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