The independence gap of a graph was introduced by Ekim et al.\ in 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 k is polynomial-time solvable if k is fixed and co-NP-complete if k is part of input. We also investigate the complexity of the independent set and independent domination problems in graph classes related to independence gap. In particular, we show that the two problems are NP-complete in the class of graphs of independence gap at most one and that the weighted independent set problem is 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, 2P3}-free graphs.

}, keywords = {Hereditary independence gap, Independent dominating set, Maximal independent set, NP-hard problem, Polynomial-time algorithm, Well-covered graph}, issn = {0012-365X}, doi = {https://doi.org/10.1016/j.disc.2020.111943}, url = {https://www.sciencedirect.com/science/article/pii/S0012365X20301321}, author = {Ekim, Tinaz and Didem G{\"o}z{\"u}pek and Ademir Hujdurovi{\'c} and Martin Milani{\v c}} } @article {1505, title = {On two extensions of equimatchable graphs}, journal = {Discrete Optimization}, volume = {26}, year = {2017}, pages = {112-130}, abstract = {A graph is said to be equimatchable if all its maximal matchings are of the same size. In this work we introduce two extensions of the property of equimatchability by defining two new graph parameters that measure how far a graph is from being equimatchable. The first one, called the matching gap, measures the difference between the sizes of a maximum matching and a minimum maximal matching. The second extension is obtained by introducing the concept of equimatchable sets; a set of vertices in a graph G is said to be equimatchable if all maximal matchings of G saturating the set are of the same size. Noting that G is equimatchable if and only if the empty set is equimatchable, we study the equimatchability defect of the graph, defined as the minimum size of an equimatchable set in it. We develop several inapproximability and parameterized complexity results and algorithms regarding the computation of these two parameters, a characterization of graphs of unit matching gap, exact values of the equimatchability defect of cycles, and sharp bounds for both parameters.

}, keywords = {Edge dominating set, Equimatchable graph, Gallai{\textendash}Edmonds decomposition, Minimum maximal matching, Parameterized complexity}, issn = {1572-5286}, doi = {https://doi.org/10.1016/j.disopt.2017.08.002}, url = {https://www.sciencedirect.com/science/article/pii/S1572528616301438}, author = {Zakir Deniz and Ekim, Tinaz and Tatiana Romina Hartinger and Martin Milani{\v c} and Mordechai Shalom} }