Faster and enhanced inclusion-minimal cograph completion

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 a...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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).
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2020.08.002