Approximating the Minimum Chain Completion problem

Abstract

A bipartite graph G = (U, V, E) is a chain graph [M. Yannakakis, Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods 2 (1) (1981) 77-79] if there is a bijection π : {1, ..., | U |} → U such that Γ (π (1)) ⊇ Γ (π (2)) ⊇ ⋯ ⊇ Γ (π (| U |)), where Γ is a function that maps a node to its neighbors. We give approximation algorithms for two variants of the Minimum Chain Completion problem, where we are given a bipartite graph G (U, V, E), and the goal is find the minimum set of edges F that need to be added to G such that the bipartite graph G′ = (U, V, E′) (E′ = E ∪ F) is a chain graph. © 2009 Elsevier B.V. All rights reserved.