Complexity and parameterized algorithms for Cograph Editing Conference Paper

abstract

• Cograph Editing is to find for a given graph G=(V,E) a set of at most k edge additions and deletions that transform G into a cograph. The computational complexity of this problem was open in the past. In this paper, we first show that this problem is NP-hard by a reduction from Exact 3-Cover. Subsequently, we present a parameterized algorithm based on a refined search tree technique with a running time of O(4.612 k+|V| 4.5), which improves the trivial algorithm of running time O(6 k+|V| 4.5). 2011 Elsevier B.V. All rights reserved.

authors

• Chen, Jianer

published proceedings

• Theoretical Computer Science

altmetric score

• 3

author list (cited authors)

• Liu, Y., Wang, J., Guo, J., & Chen, J.

citation count

• 37

complete list of authors

• Liu, Yunlong||Wang, Jianxin||Guo, Jiong||Chen, Jianer

publication date

• November 2012

publisher

• Elsevier  Publisher

published in

• Theoretical Computer Science  Journal

keywords

• Bioengineering

Digital Object Identifier (DOI)

• 10.1016/j.tcs.2011.11.040

start page

• 45

end page

• 54

volume

• 461

URL

• http%3A%2F%2Fdx.doi.org%2F10.1016%2Fj.tcs.2011.11.040