Chordal Editing is Fixed-Parameter Tractable

Yixin Cao, Dániel Marx

Research output: Journal article publicationJournal articleAcademic researchpeer-review

25 Citations (Scopus)

Abstract

Graph modification problems typically ask for a small 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 same property, one can define significantly different versions by allowing different operations. We study a very general graph modification problem that allows all three types of operations: given a graph [InlineEquation not available: see fulltext.] and integers [InlineEquation not available: see fulltext.], and [InlineEquation not available: see fulltext.], the chordal editing problem asks whether [InlineEquation not available: see fulltext.] can be transformed into a chordal graph by at most [InlineEquation not available: see fulltext.] vertex deletions, [InlineEquation not available: see fulltext.] edge deletions, and [InlineEquation not available: see fulltext.] edge additions. Clearly, this problem generalizes both chordal deletion and chordal completion (also known as minimum fill-in). Our main result is an algorithm for chordal editing in time [InlineEquation not available: see fulltext.], where [InlineEquation not available: see fulltext.] and [InlineEquation not available: see fulltext.] is the number of vertices of [InlineEquation not available: see fulltext.]. 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
Pages (from-to)118-137
Number of pages20
JournalAlgorithmica
Volume75
Issue number1
DOIs
Publication statusPublished - 1 May 2016

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Cite this