<p>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.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Path_cover" rel="nofollow noreferrer">wikipedia</a>.</p>

<p>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?</p>

CC BY-SA 3.0
2018-03-08T16:43:49.017Z
There seems to be a close connection between this problem and the one of L(2,1)-labeling (see Theorem 1 in https://www.sciencedirect.com/science/article/pii/S0166218X13000863), which seems itself to be very hard to approximate (see https://www.inderscienceonline.com/doi/abs/10.1504/IJMNDI.2006.010813?journalCode=ijmndi). Perhaps one can derive something from this connection. Both papers have their preprints accessible online.
Florent Foucaud
CC BY-SA 3.0
2018-03-09T06:12:06.280Z
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.
Chandra Chekuri
CC BY-SA 3.0
2018-03-09T12:29:47.907Z
@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$?
Bell
CC BY-SA 3.0
2018-03-12T02:58:15.563Z
@Bell See the paper https://link.springer.com/chapter/10.1007/3-540-48224-5_17 and references
Chandra Chekuri
<cc.complexity-theory><graph-theory><approximation-algorithms><approximation-hardness>
Hardness of Approximation for minimum path cover in an undirected graph?
Bell
# Hardness of Approximation for minimum path cover in an undirected graph?

(Asked by: username_0 on 2018-03-08)

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](https://en.wikipedia.org/wiki/Path_cover).

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?

**Tags:** cc.complexity-theory, graph-theory, approximation-algorithms, approximation-hardness

> **Comments:**
> **username_1**: There seems to be a close connection between this problem and the one of L(2,1)-labeling (see Theorem 1 in https://www.sciencedirect.com/science/article/pii/S0166218X13000863), which seems itself to be very hard to approximate (see https://www.inderscienceonline.com/doi/abs/10.1504/IJMNDI.2006.010813?journalCode=ijmndi). Perhaps one can derive something from this connection. Both papers have their preprints accessible online.  
> **username_2**: 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.  
> **username_0**: @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$?  
> **username_2**: @username_0 See the paper https://link.springer.com/chapter/10.1007/3-540-48224-5_17 and references  

---

## 0 answers

