Paper Info
Title
Extension of vertex cover and independent set in some classes of graphs and generalizations.
Abstract
consider extension variants of the classical graph problems Vertex Cover and Independent Set. Given a graph $G=(V,E)$ and a vertex set $U subseteq V$, it is asked if there exists a minimal vertex cover (resp. maximal independent set) $S$ with $Usubseteq S$ (resp. $U supseteq S$). Possibly contradicting intuition, these problems tend to be NP-hard, even in graph classes where the classical problem can be solved in polynomial time. Yet, we exhibit some graph classes where the extension variant remains polynomial-time solvable. also study the parameterized complexity of these problems, with parameter $|U|$, as well as the optimality of simple exact algorithms under the Exponential-Time Hypothesis. All these complexity considerations are also carried out in very restricted scenarios, be it degree or topological restrictions (bipartite, planar or chordal graphs). This also motivates presenting some explicit branching algorithms for degree-bounded instances. We further discuss the price of extension, measuring the distance of $U$ to the closest set that can be extended, which results in natural optimization problems related to extension problems for which we discuss polynomial-time approximability.
Year
Venue
Field
2018
arXiv: Computational Complexity
Discrete mathematics,Parameterized complexity,Combinatorics,Vertex (geometry),Chordal graph,Bipartite graph,Independent set,Vertex cover,Time complexity,Mathematics,Maximal independent set
DocType
Volume
Citations 
Journal
abs/1810.04629
0
PageRank 
References 
Authors
0.34
0
5
Name
Order
Citations
PageRank
Katrin Casel153.86
Henning Fernau21646162.68
Mehdi Khosravian Ghadikolaei314.10
Jérôme Monnot451255.74
Florian Sikora512414.44