Connected Vertex Cover for \((sP_1+P_5)\)-Free Graphs

The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most \(k\) that induces a connected subgraph of \(G\). This is a well-studied problem, known to be NP-complete for restricted graph classes, and, in particular, for \(H\)-free graphs if \(H\) is not a linear f...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-07
Main Authors: Johnson, Matthew, Paesani, Giacomo, Paulusma, Daniel
Format: Article
Language:English
Subjects:
Graph theory
Graphs
Polynomials
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most \(k\) that induces a connected subgraph of \(G\). This is a well-studied problem, known to be NP-complete for restricted graph classes, and, in particular, for \(H\)-free graphs if \(H\) is not a linear forest (a graph is \(H\)-free if it does not contain \(H\) as an induced subgraph). It is easy to see that Connected Vertex Cover is polynomial-time solvable for \(P_4\)-free graphs. We continue the search for tractable graph classes: we prove that it is also polynomial-time solvable for \((sP_1+P_5)\)-free graphs for every integer \(s\geq 0\).
ISSN:2331-8422