Tag Archives: Clique

Partially Ordered Knapsack

Continuing our “Variants on the Knapsack Problem” theme..

The problem: Partially Ordered Knapsack.  This is problem MP12 in the appendix.

The description: Like usual, we’re given a set U, where each element u in U has positive integer size s(u) and value v(u), a maximum total size B, and a target total value K.  We also are given a partial order \lessdot on the elements of U, which we can represent as a directed acyclic graph.  Can we find a subset U’ of U where the total size of all elements in U’ is at most B, the total value of all elements in U’ is at least K, and for all elements u in U’, if some other u’ is  \lessdot u’, then u’ is also in U’?

Example: Suppose we have the following 3 elements:

Item 1 2 3
Profit 3 3 5
Weight 3 3 5

If B=6 and K=6, and there is no partial order, then taking items 1 and 2 make a valid solution.  But if we add the partial order graph:

Than taking either item 1 or 2 means we have to also take item 3, which makes our size too big.  So this version can’t be solved.

Reduction: G&J have this as a “no reference” reduction, but I found a paper by Johnson and Neimi that has it, and I’m glad I did because it’s pretty slick.  The reduction is from Clique, So we’re given an undirected graph G=(V, E) and an integer K.   We need to build a partial order DAG (where the vertices will be knapsack items), and also sizes and values for each item.

The DAG has a vertex for each vertex and edge in G  (I’ll be talking about these as “vertices from V” and “vertices from E”)  Edges in the DAG connect vertices from V to the vertices from E that are incident on that vertex.  So there is no path of length more than 1 in the partial order (no edges come out of the vertices from E).

Both the value and size of each vertex from V are |E|+1, and the value and size of each vertex from E are 1.

B’ and K’ will both be set to K(|E|+1) + K(K-1)/2.  It’s worth noting that the first half of that equation will be the total profits and sizes of K vertices from V, and the second half will be total profits and sizes of the edges connecting those vertices if they form a clique.

Suppose we have a clique in G.  Then all of the vertices in the clique, plus all of the edges in the clique form a solution to the partially ordered knapsack problem, as described above.

If we have a solution to the Partially Ordered Knapsack problem, that means we have a set of vertices that respects the partial order with total value at least K’ and total size at most B’.  Since the value and size of each vertex are the same, that means that the total value = the total weight = K’ = B’.  The only way to get that is if we have K vertices from V, and K(K-1)/2 vertices from E.  Since the partial order is built such that we can’t take a vertex from E without taking a vertex from V that is an endpoint of the vertex from E, this means that we have a set of K(K-1)/2 edges in E that all have endpoints in one of K vertices from V, which forms a clique.

Difficulty: 5.  I like how the formula for B’ in the reduction is one where you can easily see what all of the pieces of it are doing, and where they all come from.

Protected: Conjunctive Boolean Query

This content is password protected. To view it please enter your password below:

Protected: K-Closure

This content is password protected. To view it please enter your password below:

Protected: Maximum Subgraph Matching

This content is password protected. To view it please enter your password below:

Protected: Induced Subgraph with Property π, Induced Connected Subgraph with Property π

This content is password protected. To view it please enter your password below:

Protected: Balanced Complete Bipartite Subgraph

This content is password protected. To view it please enter your password below:

Protected: Largest Common Subgraph

This content is password protected. To view it please enter your password below:

Clique

G&J don’t even bother to prove Clique is NP-Complete, just stating that it (and Independent Set) is a “different version” of Vertex Cover.  But the problem comes up often enough that it’s worth seeing in its own right.

The problem: Clique (I’ve also seen “Max Clique” or “Clique Decision Problem” (CDP))

The definition: Given a graph G=(V,E), and a positive integer J (G&J say J needs to be ≤ |V|, but I think you can allow large values and make your algorithm just say “no”).  Does J contain a subset V’ of V, or size at least J, where every two vertices in V’ are joined by an edge in E?

Example:  Using the graph we had for VC:

VC exampple

{a,c,d} form a clique of size 3.  There are no cliques of size 4, but if we add the edge (d,g) and the edge (c,h), then the vertices {c,d,g,h} would be one.

The reduction: From Vertex Cover.  Given a graph G and an integer K that is an instance of Vertex Cover, take the complement of G (the complement of a graph has the same vertices, but the set of edges is “inverted”:  (u,v) is an edge in the complement if and only if it was not an edge in G), and use it as your instance of CDP.  Set J= |V|-K

Difficulty: 3.  It’s not a 2 because it takes a little thought to see why the complement works.

Note: As stated perviously, I teach this course using the Cormen book, so in class I show Clique is NP-Hard by reducing from 3SAT.  It’s a good example of a hard reduction, probably about as hard as the VC reduction G&J do.

Vertex Cover

Back to the “core 6” with a classic problem from graph theory.  There are lots of similar graph problems, so it’s important to keep them all straight.

The Problem: Vertex Cover (VC)

The Definition: Given a graph G=(V,E) and a positive integer K (G&J say that K ≤ |V|, but really, if it’s bigger than that, you can have the algorithm just return “yes”).  Can I find a subset V’ of V, |V’| ≤ K, where every edge in E has at least one endpoint in V’?

Example: Hmm, I wonder if I can insert an image..

VC exampple

Ok, looks like that worked.  In the graph above, {c,d,g} is a vertex cover, because all edges have at least one endpoint in the set {c,d,g}.  As we’ll see later, a graph containing a clique (complete subgraph) of N nodes will need at have at least N-1 of those vertices in the cover.

The reduction: From 3SAT.  G&J on pages 54-56 show the construction.  We build a graph with vertices for all variables and their negation, with an edge between them.  We have three variables for each clause, connected in a triangle.  (The three variables correspond to “positions” in the clause).  Then there is an edge from each vertex corresponding to a literal (or its negation) to its corresponding “clause vertex”- the vertex that holds the position of that variable in the original formula.  K= # of variables + 2* number of clauses.

Difficulty: 7 , assuming it’s the first time a student has seen this sort of reduction.  If they have seen something similar (for example, a reduction from 3SAT to Clique), then maybe a 5.  The ideas are pretty similar.

Note: I teach my algorithms class using the Cormen book.  In it, they reduce 3SAT to Clique, proving Clique is NP-Complete, and then reduce Clique to VC. This works in the exact same way as the reduction from VC to Clique that I’ll be doing here next.