Co-degeneracy and Bondy and Chvátal closures: Using the complement to solve problems on dense graphs

In 1976,  Bondy and Chvátal [Discrete Math.  1976] introduced the notion of closure of a graph: let $\ell$ be an integer; the $(n+\ell)$-closure, $cl_{n+\ell}(G)$, of a graph $G$ with $n$ vertices is obtained from $G$ by recursively adding an edge between pairs of nonadjacent vertices whose degree sum is at least $n+\ell$ until no such pair remains.  
A graph property $\Upsilon$ defined on all graphs of order $n$ is said to be $(n+\ell)$-stable if for any graph $G$ of order $n$ that does not satisfy $\Upsilon$, the fact that $uv$ is not an edge of $G$ and that $G+uv$ satisfies $\Upsilon$ implies $d(u)+d(v)< n+\ell$.
The degeneracy of a graph $G$ is the least $k$ such that every induced subgraph of $G$ contains a vertex with degree at most $k$.

In this talk,  we present an algorithmic framework based on the notion of Bondy and Chvátal closures to deal with the degeneracy of the complement graph,  called co-degeneracy,  as a parameter.  Using such a framework,  we can show that Hamiltonian Path,  Hamiltonian Cycle, and Minimum Path Cover can be solved efficiently on graphs with bounded co-degeneracy.  
In addition, we show that Edge Dominating Set can also be solved efficiently on this class of graphs.  

Finally, by determining the stability of the property of having a bounded cycle cover and combining our framework with some results of Jansen et al. [WG 2019],  we show an efficient algorithm for Minimum Cycle Cover on graphs with bounded co-degeneracy.

These results show that co-degeneracy is a useful width parameter for handling dense instances of graph problems.

Everyone is welcome and encourage to attend.