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