Tag Archives: Clique

Conjunctive Boolean Query

This is another problem from the same paper as last week’s.  The paper this time though, doesn’t really give a reduction.  Hopefully, I think it’s easy enough for us to build it ourselves.

The problem: Conjunctive Boolean Query.  This is problem SR31 in the appendix.

The description: Given a conjunctive query in the format described last week, is the query true?  (That is, can we find any tuples to satisfy the query?)

Examples: Here is the “List all departments that sell pens and pencils” query from last week:

(x). Sales(x, pen) and Sales(x, pencil).

This problem would return true if there was an actual tuple in the database that could bind to x, and false otherwise.

Reduction: The paper by Chandra and Merlin that we used last week has the definition of this problem, but just says the NP-Completeness “follows from, say, the completeness of the clique problem for graphs”

But I think the reduction is pretty easy to spell out.  If we’re given an instance of Clique (a graph G and an integer K), we can just build the query:

“Does there exist k vertices x1 through xk such that all edges between any two vertices in the set exist?”

We can implement this as a database by creating a relation for all edges, and then the conjunctive query will have at most O(V2) clauses.

Dififculty: 3, but it’s a lot of work to understand the database definitions to get to the actual problem.

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.