Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width. (English) Zbl 1443.68131
Lokshtanov, Daniel (ed.) et al., 12th international symposium on parameterized and exact computation, IPEC 2017, Vienna, Austria, September 6–8, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 89, Article 21, 13 p. (2018).
Summary: We give the first polynomial-time algorithms on graphs of bounded maximum induced matching width (mim-width) for problems that are not locally checkable. In particular, we give \(n^{\mathcal{O}(w)}\)-time algorithms on graphs of mim-width at most \(w\), when given a decomposition, for the following problems: Longest Induced Path, Induced Disjoint Paths and \(H\)-Induced Topological Minor for fixed \(H\). Our results imply that the following graph classes have polynomial-time algorithms for these three problems: Interval and Bi-Interval graphs, Circular Arc, Permutation and Circular Permutation graphs, Convex graphs, \(k\)-Trapezoid, Circular \(k\)-Trapezoid, \(k\)-Polygon, Dilworth-\(k\) and Co-\(k\)-Degenerate graphs for fixed \(k\).
For the entire collection see [Zbl 1387.68026].
For the entire collection see [Zbl 1387.68026].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68W40 | Analysis of algorithms |
Keywords:
graph width parameters; dynamic programming; graph classes; induced paths; induced topological minorsReferences:
| [1] | Rémy Belmonte and Martin Vatshelle. Graph classes with structured neighborhoods and algorithmic applications. Theor. Comput. Sci., 511:54-65, 2013. doi:10.1016/j.tcs.2013. 01.011. · Zbl 1408.68109 |
| [2] | Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theoret. Comput. Sci., 511:66-76, 2013. · Zbl 1408.68111 |
| [3] | Jirí Fiala, Marcin Kaminski, Bernard Lidický, and Daniël Paulusma.The k-in-a-path problem for claw-free graphs.Algorithmica, 62(1-2):499-519, 2012.doi:10.1007/ s00453-010-9468-z. · Zbl 1236.68088 |
| [4] | Fanica Gavril.Algorithms for maximum weight induced paths.Inf. Process. Lett., 81(4):203-208, 2002. doi:10.1016/S0020-0190(01)00222-8. · Zbl 1013.68135 |
| [5] | Petr A. Golovach, Daniël Paulusma, and Erik Jan van Leeuwen. Induced disjoint paths in at-free graphs. In Fedor V. Fomin and Petteri Kaski, editors, Algorithm Theory - SWAT · Zbl 1357.68084 |
| [6] | Petr A. Golovach, Daniël Paulusma, and Erik Jan van Leeuwen. Induced disjoint paths in circular-arc graphs in linear time. Theor. Comput. Sci., 640:70-83, 2016. doi:10.1016/j. tcs.2016.06.003. · Zbl 1345.05051 |
| [7] | Petr Hlinený, Sang-il Oum, Detlef Seese, and Georg Gottlob. Width parameters beyond tree-width and their applications. Comput. J., 51(3):326-362, 2008. doi:10.1093/comjnl/ bxm052. |
| [8] | Tetsuya Ishizeki, Yota Otachi, and Koichi Yamazaki. An improved algorithm for the longest induced path problem on k-chordal graphs. Discrete Applied Mathematics, 156(15):3057- · Zbl 1186.05114 |
| [9] | Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width. ArXiv · Zbl 1442.05157 |
| [10] | Dong Yeap Kang, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle.A width parameter useful for chordal and co-comparability graphs. In Sheung-Hung Poon, · Zbl 1485.05139 |
| [11] | Ken-ichi Kawarabayashi and Yusuke Kobayashi. The induced disjoint paths problem. In Andrea Lodi, Alessandro Panconesi, and Giovanni Rinaldi, editors, Integer Programming and Combinatorial Optimization, 13th International Conference, IPCO 2008, Bertinoro, · Zbl 1143.90379 |
| [12] | Dieter Kratsch, Haiko Müller, and Ioan Todinca. Feedback vertex set and longest induced path on at-free graphs. In Hans L. Bodlaender, editor, Graph-Theoretic Concepts in Computer Science, 29th International Workshop, WG 2003, Elspeet, The Netherlands, June · Zbl 1255.05188 |
| [13] | Sridhar Natarajan and Alan P. Sprague. Disjoint paths in circular arc graphs. Nordic J. of Computing, 3(3):256-270, 1996. URL: http://dl.acm.org/citation.cfm?id=642150. |
| [14] | Neil Robertson and Paul D. Seymour. Graph minors .xiii. the disjoint paths problem. J. Comb. Theory, Ser. B, 63(1):65-110, 1995. doi:10.1006/jctb.1995.1006. · Zbl 0823.05038 |
| [15] | Sigve Hortemo Sæther and Martin Vatshelle. Hardness of computing width parameters based on branch decompositions over the vertex set. Theor. Comput. Sci., 615:120-125, 2016. · Zbl 1333.68127 |
| [16] | Jan Arne Telle and Andrzej Proskurowski.Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math., 10(4):529-550, 1997. doi:10.1137/ S0895480194275825. · Zbl 0885.68118 |
| [17] | Martin Vatshelle. New Width Parameters of Graphs. PhD thesis, University of Bergen, 2012. · Zbl 1293.05060 |
| [18] | :13 Italy, May 26-28, 2008, Proceedings, volume 5035 of Lecture Notes in Computer Science, |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
