# NP question - how to reduce this Graph problem?

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

• 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

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