Abstract (EN)

In this paper, we continue the investigation proposed in [15] about the approximability of P k partition problems, but focusing here on their complexity. More precisely, we prove that the problem consisting of deciding if a graph of nk vertices has n vertex disjoint simple paths {P 1, ⋯ ,P n } such that each path P i has k vertices is NP-complete, even in bipartite graphs of maximum degree 3. Note that this result also holds when each path P i is chordless in G[V(P i )]. Then, we prove that the optimization version of these problems, denoted by Max P 3 Packing and MaxInduced P 3 Packing, are not in PTAS in bipartite graphs of maximum degree 3. Finally, we propose a 3/2-approximation for Min3-PathPartition in general graphs within O(nm + n 2logn) time and a 1/3 (resp., 1/2)-approximation for MaxW P 3 Packing in general (resp., bipartite) graphs of maximum degree 3 within O(α(n,3n/2)n) (resp., O(n 2logn)) time, where α is the inverse Ackerman’s function and n = |V|, m = |E|.