Computing subset vertex covers in H-free graphs

Nick Brettell; Jelle J. Oostveen; Sukanya Pandey; Daniël Paulusma; Johannes Rauch; Erik Jan van Leeuwen

doi:10.1016/j.tcs.2025.115088

Computing subset vertex covers in H-free graphs

Nick Brettell, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Johannes Rauch, Erik Jan van Leeuwen^*

^*Corresponding author for this work

Sub Algorithms and Complexity

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

We consider a natural generalization of VERTEX COVER: the SUBSET VERTEX COVER problem, which is to decide for a graph G=(V,E), a subset T⊆V and integer k, if V has a subset S of size at most k, such that S contains at least one end-vertex of every edge incident to a vertex of T. A graph is H-free if it does not contain H as an induced subgraph. We solve two open problems from the literature by proving that SUBSET VERTEX COVER is NP-complete on subcubic (claw, diamond)-free planar graphs and on 2-unipolar graphs, a subclass of 2P₃-free weakly chordal graphs. Our results show for the first time that SUBSET VERTEX COVER is computationally harder than VERTEX COVER (under P≠NP). We also prove new polynomial time results, some of which follow from a reduction to VERTEX COVER restricted to classes of probe graphs. We first give a dichotomy on graphs where G[T] is H-free. Namely, we show that SUBSET VERTEX COVER is polynomial-time solvable on graphs G, for which G[T] is H-free, if H=sP₁+tP₂ and NP-complete otherwise. Moreover, we prove that SUBSET VERTEX COVER is polynomial-time solvable for (sP₁+P₂+P₃)-free graphs and bounded mim-width graphs. By combining our new results with known results we obtain a partial complexity classification for SUBSET VERTEX COVER on H-free graphs.

Original language	English
Article number	115088
Journal	Theoretical Computer Science
Volume	1032
DOIs	https://doi.org/10.1016/j.tcs.2025.115088
Publication status	Published - 29 Mar 2025

Bibliographical note

Publisher Copyright:
© 2025 The Authors

Funding

Nick Brettell was supported by the New Zealand Marsden Fund.Jelle Oostveen was supported by the NWO grant OCENW.KLEIN.114 (PACAN).Johannes Rauch was supported by the German Academic Scholarship Foundation (Studienstiftung des Deutschen Volkes).The authors declare the following financial interests/personal relationships which may be considered as potential competing interests: Jelle Oostveen reports financial support was provided by Dutch Research Council. Nick Brettell reports financial support was provided by Royal Society of New Zealand Marsden Fund. Johannes Rauch reports financial support was provided by German Academic Scholarship Foundation (Studienstiftung des Deutschen Volkes). If there are other authors, they declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Funders	Funder number
Marsden Fund
Studienstiftung des Deutschen Volkes
German Academic Scholarship Foundation
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	OCENW.KLEIN.114

Access to Document

10.1016/j.tcs.2025.115088Licence: CC BY

1-s2.0-S030439752500026X-mainFinal published version, 1.11 MBLicence: CC BY

Cite this

@article{35686698460c4b799254d2da9d1bbe2d,

title = "Computing subset vertex covers in H-free graphs",

abstract = "We consider a natural generalization of VERTEX COVER: the SUBSET VERTEX COVER problem, which is to decide for a graph G=(V,E), a subset T⊆V and integer k, if V has a subset S of size at most k, such that S contains at least one end-vertex of every edge incident to a vertex of T. A graph is H-free if it does not contain H as an induced subgraph. We solve two open problems from the literature by proving that SUBSET VERTEX COVER is NP-complete on subcubic (claw, diamond)-free planar graphs and on 2-unipolar graphs, a subclass of 2P3-free weakly chordal graphs. Our results show for the first time that SUBSET VERTEX COVER is computationally harder than VERTEX COVER (under P≠NP). We also prove new polynomial time results, some of which follow from a reduction to VERTEX COVER restricted to classes of probe graphs. We first give a dichotomy on graphs where G[T] is H-free. Namely, we show that SUBSET VERTEX COVER is polynomial-time solvable on graphs G, for which G[T] is H-free, if H=sP1+tP2 and NP-complete otherwise. Moreover, we prove that SUBSET VERTEX COVER is polynomial-time solvable for (sP1+P2+P3)-free graphs and bounded mim-width graphs. By combining our new results with known results we obtain a partial complexity classification for SUBSET VERTEX COVER on H-free graphs.",

author = "Nick Brettell and Oostveen, {Jelle J.} and Sukanya Pandey and Dani{\"e}l Paulusma and Johannes Rauch and {van Leeuwen}, {Erik Jan}",

note = "Publisher Copyright: {\textcopyright} 2025 The Authors",

year = "2025",

month = mar,

day = "29",

doi = "10.1016/j.tcs.2025.115088",

language = "English",

volume = "1032",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - Computing subset vertex covers in H-free graphs

AU - Brettell, Nick

AU - Oostveen, Jelle J.

AU - Pandey, Sukanya

AU - Paulusma, Daniël

AU - Rauch, Johannes

AU - van Leeuwen, Erik Jan

PY - 2025/3/29

Y1 - 2025/3/29

N2 - We consider a natural generalization of VERTEX COVER: the SUBSET VERTEX COVER problem, which is to decide for a graph G=(V,E), a subset T⊆V and integer k, if V has a subset S of size at most k, such that S contains at least one end-vertex of every edge incident to a vertex of T. A graph is H-free if it does not contain H as an induced subgraph. We solve two open problems from the literature by proving that SUBSET VERTEX COVER is NP-complete on subcubic (claw, diamond)-free planar graphs and on 2-unipolar graphs, a subclass of 2P3-free weakly chordal graphs. Our results show for the first time that SUBSET VERTEX COVER is computationally harder than VERTEX COVER (under P≠NP). We also prove new polynomial time results, some of which follow from a reduction to VERTEX COVER restricted to classes of probe graphs. We first give a dichotomy on graphs where G[T] is H-free. Namely, we show that SUBSET VERTEX COVER is polynomial-time solvable on graphs G, for which G[T] is H-free, if H=sP1+tP2 and NP-complete otherwise. Moreover, we prove that SUBSET VERTEX COVER is polynomial-time solvable for (sP1+P2+P3)-free graphs and bounded mim-width graphs. By combining our new results with known results we obtain a partial complexity classification for SUBSET VERTEX COVER on H-free graphs.

AB - We consider a natural generalization of VERTEX COVER: the SUBSET VERTEX COVER problem, which is to decide for a graph G=(V,E), a subset T⊆V and integer k, if V has a subset S of size at most k, such that S contains at least one end-vertex of every edge incident to a vertex of T. A graph is H-free if it does not contain H as an induced subgraph. We solve two open problems from the literature by proving that SUBSET VERTEX COVER is NP-complete on subcubic (claw, diamond)-free planar graphs and on 2-unipolar graphs, a subclass of 2P3-free weakly chordal graphs. Our results show for the first time that SUBSET VERTEX COVER is computationally harder than VERTEX COVER (under P≠NP). We also prove new polynomial time results, some of which follow from a reduction to VERTEX COVER restricted to classes of probe graphs. We first give a dichotomy on graphs where G[T] is H-free. Namely, we show that SUBSET VERTEX COVER is polynomial-time solvable on graphs G, for which G[T] is H-free, if H=sP1+tP2 and NP-complete otherwise. Moreover, we prove that SUBSET VERTEX COVER is polynomial-time solvable for (sP1+P2+P3)-free graphs and bounded mim-width graphs. By combining our new results with known results we obtain a partial complexity classification for SUBSET VERTEX COVER on H-free graphs.

UR - http://www.scopus.com/inward/record.url?scp=85216499406&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2025.115088

DO - 10.1016/j.tcs.2025.115088

M3 - Article

AN - SCOPUS:85216499406

SN - 0304-3975

VL - 1032

JO - Theoretical Computer Science

JF - Theoretical Computer Science

M1 - 115088

ER -

Computing subset vertex covers in H-free graphs

Abstract

Bibliographical note

Funding

Access to Document

Other files and links

Fingerprint

Cite this