木における賞金収集辺支配集合問題に対する多項式時間アルゴリズム

摘要

本論文では，辺支配集合問題を一般化した問題である賞金収集辺支配集合問題を扱う．賞金収集辺支配集合問題では，通常の辺支配集合問題とは異なり，全ての辺を支配することを強制されないかわりに，支配することができなかった辺に対しては罰則を払う必要がある．この間題はNP困難であることが知られており，Parekhによって8/3-近似アルゴリズムが提案されている．しかし，我々の知る限りでは，多項式時間でこの間題が解くことのできるグラフのクラスは知られていない．本論文では，木における賞金収集辺支配集合問題が多項式時間で解けることを示す．%In this paper, we consider the prize-collecting edge dominating set problem, which is a generalization of the edge dominating set problem. In the prize-collecting edge dominating set problem, we are not forced to dominate all edges, but we need to pay penalties for edges which are not dominated. It is known that this problem is NP-hard, and Parekh presented a 8/3-approximation algorithm. To the best of our knowledge, no polynomial-time solvable case is known for this problem. In this paper, we show that the prize-collecting edge dominating set problem in trees can be solved in polynomial time.