| Presentation | 2017-12-21 Maximum k-path Vertex Cover Problem on Graph Classes Tsuyoshi Yagita, Eiji Miyano, Toshiki Saitoh, Ryuhei Uehara, Tom C. van der Zanden, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Maximum k-Path Vertex Cover Problem / NP-hardness / polynomial time algorithm / split graphs / tree graphs |
| Paper # | ISEC2017-76,COMP2017-30 |
| Date of Issue | 2017-12-14 (ISEC, COMP) |
| Conference Information | |
| Committee | ISEC / COMP |
|---|---|
| Conference Date | 2017/12/21(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Eikokuji Campus, Kochi University of Technology |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Kazuto Ogawa(NHK) / Hiro Ito(Univ. of Electro-Comm.) |
| Vice Chair | Atsushi Fujioka(Kanagawa Univ.) / Shiho Moriai(NICT) / Yushi Uno(Osaka Pref. Univ.) |
| Secretary | Atsushi Fujioka(Tohoku Univ.) / Shiho Moriai(Tokai Univ.) / Yushi Uno(Seikei Univ.) |
| Assistant | Keita Emura(NICT) / Yuichi Komano(TOSHIBA) / Yuuji Suga(IIJ) |
| Paper Information | |
| Registration To | Technical Committee on Information Security / Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Maximum k-path Vertex Cover Problem on Graph Classes |
| Sub Title (in English) | |
| Keyword(1) | Maximum k-Path Vertex Cover Problem |
| Keyword(2) | NP-hardness |
| Keyword(3) | polynomial time algorithm |
| Keyword(4) | split graphs |
| Keyword(5) | tree graphs |
| 1st Author's Name | Tsuyoshi Yagita |
| 1st Author's Affiliation | Kyushu Institute of Technology(Kyutech) |
| 2nd Author's Name | Eiji Miyano |
| 2nd Author's Affiliation | Kyushu Institute of Technology(Kyutech) |
| 3rd Author's Name | Toshiki Saitoh |
| 3rd Author's Affiliation | Kyushu Institute of Technology(Kyutech) |
| 4th Author's Name | Ryuhei Uehara |
| 4th Author's Affiliation | Japan Advanced Institute of Science and Technology(JAIST) |
| 5th Author's Name | Tom C. van der Zanden |
| 5th Author's Affiliation | Utrecht University(Utrecht U.) |
| Date | 2017-12-21 |
| Paper # | ISEC2017-76,COMP2017-30 |
| Volume (vol) | vol.117 |
| Number (no) | ISEC-369,COMP-370 |
| Page | pp.pp.25-31(ISEC), pp.25-31(COMP), |
| #Pages | 7 |
| Date of Issue | 2017-12-14 (ISEC, COMP) |