Mind the independence gap
From MaRDI portal
Abstract: The independence gap of a graph was introduced by Ekim et al. (2018) as a measure of how far a graph is from being well-covered. It is defined as the difference between the maximum and minimum size of a maximal independent set. We investigate the independence gap of a graph from structural and algorithmic points of view, with a focus on classes of perfect graphs. Generalizing results on well-covered graphs due to Dean and Zito (1994) and Hujdurovi'c et al. (2018), we express the independence gap of a perfect graph in terms of clique partitions and use this characterization to develop a polynomial-time algorithm for recognizing graphs of constant independence gap in any class of perfect graphs of bounded clique number. Next, we introduce a hereditary variant of the parameter, which we call hereditary independence gap and which measures the maximum independence gap over all induced subgraphs of the graph. We show that determining whether a given graph has hereditary independence gap at most is polynomial-time solvable if is fixed and co-NP-complete if is part of input. We also investigate the complexity of the independent set problem in graph classes related to independence gap, showing that the problem is NP-complete in the class of graphs of independence gap at most one and polynomial-time solvable in any class of graphs with bounded hereditary independence gap. Combined with some known results on claw-free graphs, our results imply that the independent domination problem is solvable in polynomial time in the class of claw, 2-free graphs.
Recommendations
Cites work
- scientific article; zbMATH DE number 434906 (Why is no real title available?)
- scientific article; zbMATH DE number 3614795 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1286748 (Why is no real title available?)
- scientific article; zbMATH DE number 1472192 (Why is no real title available?)
- A characterization of graphs of girth eight or more with exactly two sizes of maximal independent sets
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Clustering and domination in perfect graphs
- Complexity results for well‐covered graphs
- Edge Dominating Sets in Graphs
- Graphs vertex-partitionable into strong cliques
- Independent Sets in Asteroidal Triple-Free Graphs
- Independent domination in chordal graphs
- Independent domination in finitely defined classes of graphs
- Independent domination in finitely defined classes of graphs: polynomial algorithms
- Linear time solvable optimization problems on graphs of bounded clique-width
- Normal hypergraphs and the perfect graph conjecture
- On almost well-covered graphs of girth at least 6
- On graphs having maximal independent sets of exactly \(t\) distinct cardinalities
- On graphs with maximal independent sets of few sizes, minimum degree at least 2, and girth at least 7
- On maximal independent sets of vertices in claw-free graphs
- On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
- Recognizing Greedy Structures
- Robust algorithms for restricted domains
- Satgraphs and independent domination. I
- Some results on graphs without long induced paths
- The ellipsoid method and its consequences in combinatorial optimization
- The structure of well-covered graphs and the complexity of their recognition problems
- WELL-COVERED GRAPHS: A SURVEY
- Well covered simplicial, chordal, and circular arc graphs
- Well-covered graphs and extendability
This page was built for publication: Mind the independence gap
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q776261)
