IEICE TRANSACTIONS on Fundamentals
Complexity of the Maximum k-Path Vertex Cover Problem
Summary :
This paper introduces the maximization version of the k-path vertex cover problem, called the MAXIMUM K-PATH VERTEX COVER problem (MaxPkVC 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 Pk includes a vertex v in a vertex set S, then we say that v or S covers Pk. Given a graph G=(V, E) and an integer s, the goal of MaxPkVC is to find a vertex subset S⊆V of at most s vertices such that the number of k-paths covered by S is maximized. The problem MaxPkVC is generally NP-hard. In this paper we consider the tractability/intractability of MaxPkVC on subclasses of graphs. We prove that MaxP3VC remains NP-hard even for split graphs. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP3VC can be solved in polynomial time.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E103-A No.10 pp.1193-1201
- Publication Date
- 2020/10/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2019DMP0014
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- complexity theory
Authors
Eiji MIYANO
Kyushu Institute of Technology
Toshiki SAITOH
Kyushu Institute of Technology
Ryuhei UEHARA
Japan Advanced Institute of Science and Technology
Tsuyoshi YAGITA
Kyushu Institute of Technology
Tom C. van der ZANDEN
the Maastricht University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Eiji MIYANO, Toshiki SAITOH, Ryuhei UEHARA, Tsuyoshi YAGITA, Tom C. van der ZANDEN, "Complexity of the Maximum k-Path Vertex Cover Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E103-A, no. 10, pp. 1193-1201, October 2020, doi: 10.1587/transfun.2019DMP0014.
Abstract: This paper introduces the maximization version of the k-path vertex cover problem, called the MAXIMUM K-PATH VERTEX COVER problem (MaxPkVC 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 Pk includes a vertex v in a vertex set S, then we say that v or S covers Pk. Given a graph G=(V, E) and an integer s, the goal of MaxPkVC is to find a vertex subset S⊆V of at most s vertices such that the number of k-paths covered by S is maximized. The problem MaxPkVC is generally NP-hard. In this paper we consider the tractability/intractability of MaxPkVC on subclasses of graphs. We prove that MaxP3VC remains NP-hard even for split graphs. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP3VC can be solved in polynomial time.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2019DMP0014/_p
Copy
@ARTICLE{e103-a_10_1193,
author={Eiji MIYANO, Toshiki SAITOH, Ryuhei UEHARA, Tsuyoshi YAGITA, Tom C. van der ZANDEN, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Complexity of the Maximum k-Path Vertex Cover Problem},
year={2020},
volume={E103-A},
number={10},
pages={1193-1201},
abstract={This paper introduces the maximization version of the k-path vertex cover problem, called the MAXIMUM K-PATH VERTEX COVER problem (MaxPkVC 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 Pk includes a vertex v in a vertex set S, then we say that v or S covers Pk. Given a graph G=(V, E) and an integer s, the goal of MaxPkVC is to find a vertex subset S⊆V of at most s vertices such that the number of k-paths covered by S is maximized. The problem MaxPkVC is generally NP-hard. In this paper we consider the tractability/intractability of MaxPkVC on subclasses of graphs. We prove that MaxP3VC remains NP-hard even for split graphs. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP3VC can be solved in polynomial time.},
keywords={},
doi={10.1587/transfun.2019DMP0014},
ISSN={1745-1337},
month={October},}
Copy
TY - JOUR
TI - Complexity of the Maximum k-Path Vertex Cover Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1193
EP - 1201
AU - Eiji MIYANO
AU - Toshiki SAITOH
AU - Ryuhei UEHARA
AU - Tsuyoshi YAGITA
AU - Tom C. van der ZANDEN
PY - 2020
DO - 10.1587/transfun.2019DMP0014
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E103-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2020
AB - This paper introduces the maximization version of the k-path vertex cover problem, called the MAXIMUM K-PATH VERTEX COVER problem (MaxPkVC 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 Pk includes a vertex v in a vertex set S, then we say that v or S covers Pk. Given a graph G=(V, E) and an integer s, the goal of MaxPkVC is to find a vertex subset S⊆V of at most s vertices such that the number of k-paths covered by S is maximized. The problem MaxPkVC is generally NP-hard. In this paper we consider the tractability/intractability of MaxPkVC on subclasses of graphs. We prove that MaxP3VC remains NP-hard even for split graphs. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP3VC can be solved in polynomial time.
ER -
English
