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

详细信息    查看全文

• 作者：Yunlong Liu (1) (2)
  Jianxin Wang (1)
  Chao Xu (1)
  Jiong Guo (3)
  Jianer Chen (1) (4)
  
  1. School of Information Science and Engineering ; Central South University ; Changsha聽 ; 410083 ; People鈥檚 Republic of China
  2. College of Mathematics and Computer Science ; Key Laboratory of High Performance Computing and Stochastic Information Processing (Ministry of Education of China) ; Hunan Normal University ; Changsha聽 ; 410081 ; People鈥檚 Republic of China
  3. Universit盲t des Saarlandes ; Campus E 1.7 ; 66123 ; Saarbr眉cken聽 ; Germany
  4. Department of Computer Science ; Texas A&M University ; College Station ; TX ; USA
  
• 关键词：Branching strategy ; Edge modification ; Multiple forbidden induced subgraph
• 刊名：Journal of Combinatorial Optimization
• 出版年：2015
• 出版时间：January 2015
• 年：2015
• 卷：29
• 期：1
• 页码：257-275
• 全文大小：567 KB
• 参考文献：1. Bessy S, Paul C, Perez A (2010) Polynomial kernels for 3-leaf power graph modification problems. Discret Appl Math 158(16):1732鈥?744 CrossRef
  2. Bessy S, Perez A (2011) Polynomial kernels for proper interval completion and related problems. In: Proceedings of 18th international symposium on fundamentals of computer theory, vol 6914. Lecture Notes in Computer Science, pp 229鈥?39
  3. Brandst盲da A, Le VB, Spinrad JP (1999) Graph classes: a survey (monographs on discrete mathematics and applications). SIAM, Philadelphia CrossRef
  4. Cai L (1996) Fixed-parameter tractability of graph modification problems for hereditary properties. Inf Process Lett 58(4):171鈥?96 CrossRef
  5. Downey R, Fellows M (1999) Parameterized complexity. Springer-Verlag, Berlin CrossRef
  6. Dom M, Guo J, H眉ffner F, Niedermeier R (2006) Error compensation in leaf power problems. Algorithmica 44(4):363鈥?81 CrossRef
  7. Feng Q, Wang J, Chen J (2014) Matching and weighted P2-packing: algorithms and kernels. Theor Comput Sci 522:85鈥?4
  8. Gramm J, Guo J, H眉ffner F, Niedermeier R (2004) Automated generation of search tree algorithms for hard graph modification problems. Algorithmica 39(4):321鈥?47 CrossRef
  9. Guo J, H眉ffner F, Komusiewicz C, Zhang Y (2008) Improved algorithms for bicluster editing. In: Proceedings of 5th theory and applications of models of computation, vol 4978. Lecture Notes in Computer Science, pp 445鈥?56
  10. Guo J (2007) Problem kernels for NP-complete edge modification problems: split and related graphs. In: Proceedings of 18th international symposium on algorithms and computation, vol 4835. Lecture Notes in Computer Science, pp 915鈥?26
  11. Kaplan H, Shamir R, Tarjan RE (1999) Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput. 28(5):1906鈥?922 CrossRef
  12. Liu Y, Wang J, Guo J, Chen J (2012) Complexity and parameterized algorithms for cograph editing. Theor Comput Sci 461:45鈥?4 CrossRef
  13. Nastos J, Gao Y (2010) A novel branching strategy for parameterized graph modification problems. In: Proceedings of 4th annual international conference on combinatorial optimization and applications, vol 6509. Lecture Notes in Computer Science, pp 332鈥?46
  14. Niedermeier R, Rossmanith P (2000) A general method to speed up fixed-parameter tractable algorithms. Inf Process Lett 73:125鈥?29 CrossRef
  15. Sharan R (2002) Graph modification problems and their applications to genomic research. PhD thesis, Tel-Aviv University
  16. Villanger Y (2010a) Proper interval vertex deletion. Presentation in the 5th international symposium on parameterized and exact computation. http://www.lirmm.fr/~paul/ANR/CIRM-TALKS-2010/Villanger-cirm-2010.pdf
  17. Villanger Y (2010b) Proper interval vertex deletion. In: Proceedings of the 5th international symposium on parameterized and exact computation, vol 6478. Lecture Notes in Computer Science, pp 228鈥?38
  18. Wang J, Tan P, Yao J, Feng Q, Chen J (2013) On the minimum link-length rectilinear spanning path problem: complexity and algorithms. IEEE Trans Comput. doi:10.1109/TC.2013.163
  19. Wegner G (1967) Eigenschaften der Nerven homologisch-einfacher Familien im \(R^{n}\) . PhD thesis, Universit盲t G枚ttingen
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

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.