Characterizing and computing minimal cograph completions

A cograph completion of an arbitrary graph GG is a cograph supergraph of GG on the same vertex set. Such a completion is called minimal if the set of edges added to GG is inclusion minimal. In this paper we present two results on minimal cograph completions. The first is a characterization that allows us to check in linear time whether a given cograph completion is minimal. The second result is a vertex incremental algorithm to compute a minimal cograph completion HH of an arbitrary input graph GG in O(|V(H)|+|E(H)|)O(|V(H)|+|E(H)|) time. An extended abstract of the result has been already presented at FAW 2008 [D. Lokshtanov, F. Mancini, C. Papadopoulos, Characterizing and computing minimal cograph completions, in: Proceedings of FAW’08–2nd International Frontiers of Algorithmics Workshop, in: LNCS, vol. 5059, 2008, pp. 147158. [1]].