An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs

abstract

• 2014, Springer Science+Business Media New York. Branching on forbidden induced subgraphs is a genetic strategy to obtain parameterized algorithms for many edge modification problems. For such a problem in which the graph property is defined by multiple forbidden induced subgraphs, branching process is trivially performed on each subgraph. Thus, the size of the resulting search tree is dominated by the size of the largest forbidden subgraph. In this paper, we present a simple strategy for deriving significantly improved branching rules to deal with multiple forbidden subgraphs by edge modifications. The basic idea hereby is that while constructing branching rules for the largest forbidden subgraph, we sufficiently take into account the structural relationship between it and other forbidden subgraphs. By applying this strategy, we obtain improved parameterized algorithms for edge modification problems for several graph properties such as 3-leaf power, proper interval, threshold and co-trivially perfect graphs.

authors

• Chen, Jianer

published proceedings

• JOURNAL OF COMBINATORIAL OPTIMIZATION

author list (cited authors)

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

citation count

• 4

complete list of authors

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

publication date

• January 2015

publisher

• Springer Nature  Publisher

published in

• Journal of Combinatorial Optimization  Journal

keywords

• Branching Strategy
• Edge Modification
• Multiple Forbidden Induced Subgraph

Digital Object Identifier (DOI)

• 10.1007/s10878-014-9733-1

start page

• 257

end page

• 275

volume

• 29

issue

• 1

URL

• http://dx.doi.org/10.1007/s10878-014-9733-1