CODEWITHSUNDEEP
algorithmnpnp-completenp-hard
sv_jan5
sv_jan5

Reputation: 1573

Proving NP completeness of optimal path cover

This paper solves the optimal path cover problem for block graphs or bipartite permutation graph. In the third line of its introduction it's written that optimal path cover problem is NP-Complete and has given reference to "Computer and intractability: a guide to the theory of NP-completeness by David S. Johnson, Michael R. Garey". But I couldn't find its proof in the book. If anyone knows how to prove NP-Completeness of this problem then share your solution.

Optimal path cover problem:
Given a graph G, find a minimum number of vertex disjoint paths which together cover all the vertices of the graph.

Upvotes: 0

Views: 490

Answers (1)

user555045
user555045

Reputation: 64913

Considering the obvious decision variant (ie given k, is there a cover with k paths)

OPC(k=1) detects Hamiltonian paths, so clearly it's NP-hard.

It's also in NP because given the paths, checking whether they're disjoint and covering is easy.

Upvotes: 2

Related Questions