Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Complexity of the Maximum k-Path Vertex Cover Problem
verfasst von : Eiji Miyano, Toshiki Saitoh, Ryuhei Uehara, Tsuyoshi Yagita, Tom C. van der Zanden
Erschienen in: WALCOM: Algorithms and Computation
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
This paper introduces the maximum version of the k-path vertex cover problem, called the Maximum k-Path Vertex Cover problem (\(\mathsf{{Max}}{P_k}\mathsf{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 \(\mathsf{{Max}}{P_k}\mathsf{VC}\) is to find a vertex subset \(S\subseteq V\) of at most s vertices such that the number of k-paths covered by S is maximized. \(\mathsf{{Max}}{P_k}\mathsf{VC}\) is generally NP-hard. In this paper we consider the tractability/intractability of \(\mathsf{{Max}}{P_k}\mathsf{VC}\) on subclasses of graphs: We prove that \(\mathsf{{Max}}{P_3}\mathsf{VC}\) and \(\mathsf{{Max}}{P_4}\mathsf{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 \(\mathsf{{Max}}{P_3}\mathsf{VC}\) can be solved in polynomial time.