| 著者 |
Kobayashi, Kenya
Lin, Guohui
宮野, 英次
斎藤, 寿樹
Suzuki, Akira
Utashima, Tadatoshi
Yagita, Tsuyoshi
|
|
内容記述 |
For a graph G=(V,E), a collection P of vertex-disjoint (simple) paths is called a path cover of G if every vertex v∈V is contained in exactly one path of 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,…,n−1}. Given a graph G=(V,E) and a weight function f:U→R∪{+∞,−∞}, which defines a weight for each path in its length, MinPC (MaxPC) is to find a path cover P of G such that the total weight of the paths in P is minimized (maximized). Let L be a subset of U, and PL be the set of paths such that each path is of length ℓ∈L. We especially consider MinPLPC with 0–1 cost, i.e., the cost function is f(ℓ)=1 if ℓ∈L; otherwise f(ℓ)=0. We also consider MaxPLPC with f(ℓ)=ℓ+1, if ℓ∈L; otherwise f(ℓ)=0. That is, MaxPLPC is to maximize the number of vertices contained in the paths with length ℓ∈L in a path cover. In this paper, we first show that MinP{0,1,2}PC is NP-hard for planar bipartite graphs of maximum degree three. This implies that (i) for any constant σ≥1, there is no polynomial-time approximation algorithm with approximation ratio σ for MinP{0,1,2}PC unless P=NP, and (ii) MaxP{3,…,n−1}PC is NP-hard for the same graph class. Next, (iii) we present a polynomial-time algorithm for MinP{0,1,…,k}PC on graphs with bounded treewidth for a fixed k. Lastly, (iv) we present a 4-approximation algorithm for MaxP{3,…,n−1}PC, which becomes a 2.5-approximation for subcubic graphs. |
10391214.pdf (436 KB)
