Edge deletion problems: Branching facilitated by modular decomposition

Yunlong Liu, Jianxin Wang, Jie You, Jianer Chen, Yixin Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

Abstract

Edge deletion problems ask for a minimum set of edges whose deletion makes a graph have a certain property. When this property can be characterized by a finite set of forbidden induced subgraphs, the problem can be solved in fixed-parameter time by a naive bounded search tree algorithm. Sometimes deleting an edge to break an erstwhile forbidden induced subgraph might introduce new ones, which may involve the neighbors of the original forbidden induced subgraph. Therefore, in considering possible ways to break a forbidden induced subgraph one naturally takes its neighborhood into consideration. This observation easily yields more efficient branching rules, but a naive implementation will require too many tedious case analyses. Here we take advantage of modular decomposition, which allows us to focus on far simpler quotient graphs instead of the original graphs. They together yield simple improved algorithms for the edge deletion problems to chain graphs and trivially perfect graphs.
Original languageEnglish
Pages (from-to)63-70
Number of pages8
JournalTheoretical Computer Science
Volume573
DOIs
Publication statusPublished - 30 Mar 2015

Keywords

  • Branching
  • Chain graphs
  • Edge deletion problems
  • Graph modification problems
  • Modular decomposition
  • Trivially perfect graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this