講演抄録/キーワード |
講演名 |
2017-03-07 11:30
Extension of the Vertex Cover Problem to the Size-t Cycle Cover Problems ○Batchunag Dashdemberel・Osamu Watanabe(Tokyo Tech.) COMP2016-52 |
抄録 |
(和) |
グラフ頂点被覆(略称 VC)問題の拡張を考える.
グラフの全ての辺に対して,
その辺上の頂点を 1 つ以上を含む頂点部分集合が
(辺の)頂点被覆(略称,VC)である.
この概念を拡張し,
パラメータ $t$ に対し,
「サイズ-$t$ のサイクルの頂点被覆集合」(略称,$vcct$)を考える.
頂点数 $t$ のサイクル全てに対して,
そのサイクル上の頂点を 1 つ以上を含む頂点部分集合である.
本論文では,
与えられたグラフに対し,
頂点数最小の $vcct$ を求める問題(略称,$vcct$ 問題)を考え,
任意の $tge2$ に対し,
この問題の NP-困難性を示した.
さらに,
とくに $t=4$ の場合に,
木幅が $k$ 以下のグラフ対して
(木分解が与えられたもとで)
$vccfour$ 問題を,
$2^k cdot sqrt{12}^{k^2} cdot O(k^5n)$-時間で解くアルゴリズムを提案した. |
(英) |
We consider an extension of the Vertex Cover (VC) problem.
For a given graph,
its (edge) vertex cover (in short, VC) is a set of vertices
that has at least one end point for every edge of the graph.
For a specified parameter $t$,
we introduce the notion of ``size-$t$ cycle cover''
(in short, $vcct$),
which means a set of vertices
that has at least one vertex for every cycle consisting of $t$ vertices.
We consider the problem of computing
the mini size $vcct$ (in short, the $vcct$ problem),
and show that, for any $tge2$,
the NP-hardness of the problem.
For the case $t=4$,
we show an algorithm
that solves the $vccfour$ problem for any treewidth $k$ graph
in
$2^k cdot sqrt{12}^{k^2} cdot O(k^5n)$-time
(when a tree decomposition is given as an input). |
キーワード |
(和) |
vertex cover problem / cycle cover / bounded treewidth / FPT algorithm / / / / |
(英) |
vertex cover problem / cycle cover / bounded treewidth / FPT algorithm / / / / |
文献情報 |
信学技報, vol. 116, no. 503, COMP2016-52, pp. 11-18, 2017年3月. |
資料番号 |
COMP2016-52 |
発行日 |
2017-02-28 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2016-52 |