The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cet article présente la version de maximisation du k-problème de couverture des sommets du chemin, appelé MMAXIMUM K-PATH VERTEX COVER problème (MaxPkVC en abrégé) : Un chemin composé de k sommets, c'est-à-dire un chemin de longueur k-1 s'appelle un k-chemin. Si un k-chemin Pk comprend un sommet v dans un ensemble de sommets S, alors nous disons que v or S couvre Pk. Étant donné un graphique G=(V, E) et un entier s, le but de MaxPkVC consiste à trouver un sous-ensemble de sommets S⊆V d'au plus s sommets tels que le nombre de k-les chemins parcourus par S est maximisée. Le problème MaxPkVC est généralement NP-difficile. Dans cet article, nous considérons la traitabilité/intraitabilité de MaxPkVC sur les sous-classes de graphiques. Nous prouvons que MaxP3VC reste NP-difficile même pour les graphiques fractionnés. De plus, si le graphique d'entrée est limité aux graphiques avec une largeur d'arbre délimitée constante, alors MaxP3VC peut être résolu en temps polynomial.
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
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.
Copier
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
Copier
@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},}
Copier
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 -