2
$\begingroup$

I am losing my head on Algorithms (namely P-NP stuff) and I thought I would pop over here.

I have a question: in my last exam (which went rather bad :/ ) there was a question which was on the line "given a graph G(V,E), can we check whether it has a subset which contains a k-clique and a chain of length k?"

I am not sure whether I did it right, so I want to check.

I thought that since it has a clique, it is basically reducible to a clique because we just need to find a clique and then search, in polynomial time, each vertex if it has k-chain.

EDIT: A chain of size K:

Each vertex in the chain is connected only to another vertex by an edge. So, the degree of each vertex is 1. And |V| = k. [and one of the vertices connects to another vertex which is part of the clique].

$\endgroup$
  • $\begingroup$ Each vertex in the chain is connected only to another vertex by an edge. So, the degree of each vertex is 1. And |V| = k. [and one of the vertices connects to another vertex which is part of the clique]. $\endgroup$ – N3sh Jan 21 '14 at 20:30
  • $\begingroup$ So why not just look for all disjoint subsets $S_1,S_2$ of size $k$ and check if $S_1$ is a clique and $S_2$ a chain which is connected to the clique? That is polynomial in $n$ if you fix $k$. $\endgroup$ – Listing Jan 21 '14 at 20:37
0
$\begingroup$

The problem of finding a clique is NP-complete, if $k$ is part of the input and not fixed. So your goal is to reduce your problem to the one where you just have to find a $k$-clique.

For instance you can add $k$ vertices $x_1,\dots x_k$ to your graph that for a chain, and plug $x_1$ to all the vertices in your graph. This yields a graph $G'$ such that $G'$ has a $k$-clique and a $k$-chain iff your original graph $G$ has a $k$-clique. So if you had an algorithm in $P$ for your problem, this would give an algorithm in $P$ for CLIQUE.

This means your problem is $NP$-complete.

$\endgroup$
  • $\begingroup$ I am not sure if I understood the answer correctly. Basically, I take an instance of G (G'), I add K vertices and connect them to all the rest. How do I prove that there is a k-clique and chain k-long? $\endgroup$ – N3sh Jan 21 '14 at 20:54
  • $\begingroup$ The goal is to build $G'$ for $G$ such that if $G$ has a $k$-clique, then $G'$ has a $k$-clique and a $k$-chain (which is your problem if I got it correctly, let's call it CLIQUECHAIN). This means if you can answer CLIQUECHAIN for $G'$, then you can also answer CLIQUE for $G$, which is an NP-complete problem. So CLIQUECHAIN is also NP-complete. $\endgroup$ – Denis Jan 21 '14 at 20:57
  • $\begingroup$ Don't I have to build G' such that if G' has a k-clique then G has a CLIQUECHAIN? [probably naming issue] If so, I understand the goal; but I can't really think of a way to reach that goal. How do I modify G in such a way we can create a k-clique on the other iff G has a CLIQUECHAIN? $\endgroup$ – N3sh Jan 21 '14 at 21:01
  • $\begingroup$ No I did it the right way: you want to prove that an algorithm for CLIQUECHAIN would also solve the CLIQUE problem. This means that you need to be able to transform a CLIQUE instance into a CLIQUECHAIN instance with same answer. $\endgroup$ – Denis Jan 21 '14 at 21:02
  • $\begingroup$ Ok! Now I got it! But how do I finally prove that by adding a chain with k-vertices and k-edges to G (and thus creating G'), I always have a correct answer? $\endgroup$ – N3sh Jan 21 '14 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.