Chordal editing is fixed-parameter tractable

Yixin Cao, Dániel Marx

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

14 Citations (Scopus)

Abstract

Graph modification problems are typically asked as follows: is there a set of κ operations that transforms a given graph to have a certain property. The most commonly considered operations include vertex deletion, edge deletion, and edge addition; for the ame property, one can define significantly different versions by allowing different operations. We study a very general graph modification problem which allows all three types of operations: given a graph G and integers κ1, κ2, and κ3, the chordal editing problem asks if G can be transformed into a chordal graph by at most κ1vertex deletions, κ2edge deletions, and κ3edge additions. Clearly, this problem generalizes both chordal vertex/edge deletion and chordal completion (also known as minimum fill-in). Our main result is an algorithm for chordal editing in time 2O(k log k)· nO(1), where κ := κ1+ κ2+ κ3; therefore, the problem is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm is both more efficient and conceptually simpler than the previously known algorithm for the special case chordal deletion.
Original languageEnglish
Title of host publicationLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages214-225
Number of pages12
Volume25
ISBN (Electronic)9783939897651
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014 - Lyon, France
Duration: 5 Mar 20148 Mar 2014

Conference

Conference31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014
Country/TerritoryFrance
CityLyon
Period5/03/148/03/14

Keywords

  • Chordal completion
  • Chordal deletion
  • Chordal graph
  • Clique tree decomposition
  • Graph modification problems
  • Holes
  • Parameterized computation
  • Simplicial vertex sets

ASJC Scopus subject areas

  • Software

Cite this