Path Cover Problems with Length Cost
Kenya Kobayashi, Guohui Lin, Eiji Miyano, Toshiki Saitoh, Akira Suzuki, Tadatoshi Utashima, Tsuyoshi Yagita · Lecture notes in computer science · 2022
For a graph $$G=(V,E)$$ , a collection $$\mathcal {P}$$ of vertex-disjoint (simple) paths is called a path cover of G if every vertex $$v\in V$$ is contained in exactly one path of $$\mathcal {P}$$ . The Path Cover problem (PC for short) is to find a minimum cardinality path cover of G. In this paper, we introduce generalizations of PC, where each path is associated with a weight (cost or profit). Our problem, Minimum (Maximum) Weighted Path Cover (MinPC (MaxPC)), is defined as follows: Let $$U=\{0,1,\dots ,n-1\}$$ . Given a graph $$G=(V,E)$$ and a weight function $$f:U\rightarrow \mathbb {R}\cup \{+\infty , -\infty \}$$ , which defines a weight for each path in its length, MinPC (MaxPC) is to find a path cover $$\mathcal {P}$$ of G such that the total weight of the paths in $$\mathcal {P}$$ is minimized (maximized). Let L be a subset of U, and $$P^{L}$$ be the set of paths such that each path is of length $$\ell \in L$$ . We especially consider $$\textsf {Min}P^{L}\textsf {PC}$$ with 0–1 cost, i.e., the cost function is $$f(\ell ) = 1$$ if $$\ell \in L$$ ; otherwise $$f(\ell ) = 0$$ . We also consider $$\textsf {Max}P^{L}\textsf {PC}$$ with $$f(\ell ) = \ell +1$$ , if $$\ell \in L$$ ; otherwise $$f(\ell ) = 0$$ . That is, $$\textsf {Max}P^{L}\textsf {PC}$$ is to maximize the number of vertices contained in the paths with length $$\ell \in L$$ in a path cover. In this paper, we first show that $$\textsf {Min}P^{\{0,1,2\}}\textsf {PC}$$ is NP-hard for planar bipartite graphs of maximum degree three. This implies that (i) for any constant $$\sigma \ge 1$$ , there is no polynomial-time approximation algorithm with approximation ratio $$\sigma $$ for $$\textsf {Min}P^{\{0,1,2\}}\textsf {PC}$$ unless P $$=$$ NP, and (ii) $$\textsf {Max}P^{\{3,\dots ,n-1\}}\textsf {PC}$$ is NP-hard for the same graph class. Next, (iii) we present a polynomial-time algorithm for $$\textsf {Min}P^{\{0,1,\dots ,k\}}\textsf {PC}$$ on graphs with bounded treewidth for a fixed k. Lastly, (iv) we present a 4-approximation algorithm for $$\textsf {Max}P^{\{3,\dots ,n-1\}}\textsf {PC}$$ , which becomes a 2.5-approximation for subcubic graphs.