Faster and enhanced inclusion-minimal cograph completion

• Published in: Discrete Applied Mathematics 2021-01, Vol.288, p.138-151
• Main Authors: Crespelle, Christophe, Lokshtanov, Daniel, Phan, Thi Ha Duong, Thierry, Eric
• Format: Article
• Language: English
• Subjects: Algorithms; Cograph; Complexity; Computer Science; Edge modification; Graph theory; Graphs; Minimal completion
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2020.08.002

We design two incremental algorithms for computing an inclusion-minimal completion of an arbitrary graph into a cograph. The first one is able to do so while providing an additional property which is crucial in practice to obtain inclusion-minimal completions using as few edges as possible : it is able to compute a minimum-cardinality completion of the neighbourhood of the new vertex introduced at each incremental step. It runs in O(n+m′) time, where m′ is the number of edges in the completed graph. This matches the complexity of the algorithm in (Lokshtanov et al., 2010) and positively answers one of their open questions. Our second algorithm improves the complexity of inclusion-minimal completion to O(n+mlog2n) when the additional property above is not required. Moreover, we prove that many very sparse graphs, having only O(n) edges, require Ω(n2) edges in any of their cograph completions. For these graphs, which include many of those encountered in applications, the improvement we obtain on the complexity scales as O(n∕log2n).