Long chain of friends

Question

You are given a list of people, and statements of the form “x knows y”.  You are asked to find, is there a chain of k people, such as x₁ knows x₂, x₂ knows x₃,   and x_k-1 knows x_k.  Prove that this problem is NP-complete by using one of the known NP-complete problems (CLIQUE, 3-SAT, Hamiltonian Path, Hamiltonian Cycle, Independent Set, etc.) 

Answer 1

NP-Completeness Proof

1) The long chain of friends is in NP. We can check a given solution to the long chain of friends problem in polynomial time by iterating through each node and verifying that all nodes are connected and any given node is connected only to its neighbors (e.g. x1 is connected to x2, x2 is connected to x1 and xj, xj is connected to xj-1 and xj+1, and xn is connected to xn-1).

2) Hamiltonian Path is a known NP-Complete problem.

3) Suppose a given graph G. If we can find a Hamiltonian Path in G, we have also found the long chain of friends solution, as the long chain of friends is a generalization of a Hamiltonian Path. Therefore, we can reduce the Hamiltonian Path problem to the Long Chain of Friends problem, demonstrating that the long chain of friends is NP-complete.

Answer 2

To prove that the problem is NP-complete we have to prove two things.

Firstly, we need to prove that the problem lies in NP.

Proof: To prove that the problem lies in NP we need to prove that given a certificate for the problem we can verify in polynomial time if the certificate is correct or not. So given a chain of k nodes we need to check if xi knows x(i+1) for all 0<=i<k.

We can do this by traversing each of the nodes in the list and checking in the adjacency matrix of the graph is the xi and x(i+1) nodes are adjacent to each other. This can be done in polynomial time, to be precise in O(k).

Secondly, we need to prove that all problems in NP can be reduced to this problem.

To prove this we show that Hamiltonian Path can be reduced to the above problem.

We prove by the method of contradiction. Let's assume that the above problem lies in P.

Then we can find if a chain of length k exists in a graph in time t.

Let's assume that there are n nodes in the graph. Then we can find in polynomial time if there exists a chain of length n.

Which is exactly a hamiltonian path in the graph.

So If we can solve the above problem in P then Hamiltonian path problem can also be solved in P.

Which is a contradiction. Therefore The above problem must also lie in NP.

Answer 3

Given a list of people Is there a chain of length K. Let's represent this problem using graphs. People be considered as vertices and if" x know y" then there is an edge between x and y. Hence the problem statement can be rewritten as for a given graph is there k connected vertices.

We can reduce the above problem to a Hamiltonian path problem. A Hamiltonian path problem can be stated as given a graph G (V E), is there a path connect all the vertices exactly once.

For a given graph G if there is sub-graph with K number of nodes with a Hamiltonian path then the graph contains a chain of length K. Hence the problem is reducible to Hamiltonian path problem which is NP-complete, so the chain problem is also NP-complete.

Answer 4

A chain of friends that is of length n is essentially a Hamiltonian Path.

Therefore, the “long chain of friends” problem is a generalization of the Hamiltonian Path problem.

The reduction diagram can be drawn from the Hamiltonian Path to a Long chain of friends problem by instantiating the value of k = n.