講演抄録/キーワード |
講演名 |
2017-12-21 11:50
部分グラフクラス上での最大k-パス頂点被覆問題 ○八木田 剛・宮野英次・斎藤寿樹(九工大)・上原隆平(北陸先端大)・Tom C. van der Zanden(ユトレヒト大) ISEC2017-76 COMP2017-30 |
抄録 |
(和) |
本論文では,$k$-パス頂点被覆問題の最大化問題,最大$k$-パス頂点被覆問題(textsf{Max$P_k$VC}問題)を新たに導入する.$k$頂点による道(パス),すなわち距離が$k-1$となるような道は$k$-パスと呼ばれる.もし$k$-パス$P_k$上に,頂点集合$S$中の点$v$が含まれているならば,集合$S$もしくは頂点$v$が$P_k$を被覆するという.グラフ$G=(V,E)$と整数$s$が与えられたとき,textsf{Max$P_k$VC}問題は,被覆された$k$-パスの本数が最大となるような$s$個の頂点による頂点部分集合$Ssubseteq V$を見つけることを目的とする問題である.textsf{Max$P_k$VC}問題は一般的にNP-困難な問題である.本論文では入力グラフを部分グラフに限定したときのtextsf{Max$P_k$VC}問題の計算困難性/容易性を考える.本論文ではtextsf{Max$P_3$VC}問題とtextsf{Max$P_4$VC}問題がそれぞれスプリットグラフ,弦グラフを入力とした時でさえもNP-困難のままであることを示す.更に,入力グラフの木幅が定数に限定されているときに,textsf{Max$P_3$VC}問題を多項式時間で解くことのできるアルゴリズムも示す. |
(英) |
This paper introduces the maximum version of the $k$-path vertex cover problem, called the textsc{Maximum $k$-Path Vertex Cover} problem (textsf{Max$P_k$VC} for short): A path consisting of $k$ vertices, i.e., a path of length $k-1$ is called a $k$-path. If a $k$-path $P_k$ includes a vertex $v$ in a vertex set $S$, then we say that $S$ or $v$ covers $P_k$. Given a graph $G = (V, E)$ and an integer $s$, the goal of textsf{Max$P_k$VC} is to find a vertex subset $Ssubseteq V$ of at most $s$ vertices such that the number of $k$-paths covered by $S$ is maximized. textsf{Max$P_k$VC} is generally NP-hard. In this paper we consider the tractability/intractability of textsf{Max$P_k$VC} on subclasses of graphs: We prove that textsf{Max$P_3$VC} and textsf{Max$P_4$VC} remain NP-hard even for split graphs and for chordal graphs, respectively. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then textsf{Max$P_3$VC} can be solved in polynomial time. |
キーワード |
(和) |
最大k-パス頂点被覆問題 / NP-困難性 / 多項式時間アルゴリズム / スプリットグラフ / 木グラフ / / / |
(英) |
Maximum k-Path Vertex Cover Problem / NP-hardness / polynomial time algorithm / split graphs / tree graphs / / / |
文献情報 |
信学技報, vol. 117, no. 370, COMP2017-30, pp. 25-31, 2017年12月. |
資料番号 |
COMP2017-30 |
発行日 |
2017-12-14 (ISEC, COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
ISEC2017-76 COMP2017-30 |
|