3
$\begingroup$

Given an undirected graph $G = (V,E)$, a path cover is a set of disjoint paths such that every vertex $v\in V$ belongs to exactly one path. The minimum path cover problem consists of finding a path cover of $G$ having the least number of paths.

One can show the minimum path cover problem is NP-hard by a reduction from Hamiltonian path: a minimum path cover consists of one path if and only if there is a Hamiltonian path in $G$. This reduction is shown in wikipedia.

But is there any result showing the hardness of approximation for minimum path cover in an undirected graph? e.g., what is the best approximation ratio a polynomial-time algorithm can achieve?

|cite|improve this question
$\endgroup$
  • $\begingroup$ There seems to be a close connection between this problem and the one of L(2,1)-labeling (see Theorem 1 in sciencedirect.com/science/article/pii/S0166218X13000863), which seems itself to be very hard to approximate (see inderscienceonline.com/doi/abs/10.1504/…). Perhaps one can derive something from this connection. Both papers have their preprints accessible online. $\endgroup$ – Florent Foucaud Mar 8 '18 at 16:43
  • 1
    $\begingroup$ TSP (and hence also TSP-Path) in metrics with distances 1 and 2 is APX-hard. That is, given a complete graph in which each edge cost is either 1 or 2, it is NP-Complete to distinguish whether there is a Hamiltonian path of length $n-1$ or whether the shortest Hamiltonian path is at least $(1+\delta)n$ where $\delta > 0$ is a fixed constant. It seems that one can use this to show that the problem of finding the minimum path cover is hard to approximate to within a $\delta n$ factor. $\endgroup$ – Chandra Chekuri Mar 9 '18 at 6:12
  • $\begingroup$ @ChandraChekuri Thanks! Do you have the reference which shows that it is NP-Complete to distinguish between $n - 1$ and $(1 + \delta) n$ for some constant $\delta > 0$? $\endgroup$ – Bell Mar 9 '18 at 12:29
  • $\begingroup$ @Bell See the paper link.springer.com/chapter/10.1007/3-540-48224-5_17 and references $\endgroup$ – Chandra Chekuri Mar 12 '18 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.