| 著者 |
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∪ { + ∞, - ∞} that defines a weight for each path based on its length, the objective of 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 consider MinPLPC with binary 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. Many well-known graph theoretic problems such as the Hamiltonian Path and the Maximum Matching problems can be modeled using MinPLPC and MaxPLPC. In this paper, we first show that deciding whether MinP{ 0 , 1 , 2 }PC has a 0-weight solution is NP-complete for planar bipartite graphs of maximum degree three, and consequently, (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, we present a polynomial-time algorithm for MinP{,1,⋯,k}PC on graphs with bounded treewidth for a fixed k. Lastly, we present a 4-approximation algorithm for MaxP{3,⋯,n-1}PC, which becomes a 2.5-approximation algorithm for subcubic graphs. |
10406890.pdf (1.4 MB)
