2

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].

N3sh
  • 181
  • 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]. – N3sh Jan 21 '14 at 20:30
  • 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$. – Listing Jan 21 '14 at 20:37

1 Answers1

1

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.

Denis
  • 6,945
  • 1
  • 21
  • 22
  • 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? – N3sh Jan 21 '14 at 20:54
  • 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. – Denis Jan 21 '14 at 20:57
  • 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? – N3sh Jan 21 '14 at 21:01
  • 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. – Denis Jan 21 '14 at 21:02
  • 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? – N3sh Jan 21 '14 at 21:11
  • Because in $G'$ the chain part is always satisfied, so just the clique part remains. – Denis Jan 21 '14 at 21:11
  • Thanks a lot, I think I got it! :D Is there some chat for this kind of questions? – N3sh Jan 21 '14 at 21:16
  • There is the chat os stackexchange, link on the left – Denis Jan 21 '14 at 21:22
  • Any specific room? – N3sh Jan 21 '14 at 21:23
  • for instance "mathematics" – Denis Jan 21 '14 at 21:25