Contraction obstructions for treewidth. (English) Zbl 1223.05022
Summary: We provide two parameterized graphs \(\varGamma _{k}, \varPi _{k}\) with the following property: for every positive integer \(k\), there is a constant \(c_{k}\) such that every graph \(G\) with treewidth at least \(c_{k}\), contains one of \(K_{k}, \varGamma _{k}, \Pi _{k}\) as a contraction, where \(K_{k}\) is a complete graph on \(k\) vertices. These three parameterized graphs can be seen as “obstruction patterns” for the treewidth with respect to the contraction partial ordering. We also present some refinements of this result along with their algorithmic consequences.
References:
| [1] | Bodlaender, H.; Fomin, F.; Lokshtanov, D.; Penninkx, E.; Saurabh, S.; Thilikos, D., (Meta) kernelization, (Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009 (2009), IEEE Comput. Soc.), 629-638 · Zbl 1292.68089 |
| [2] | Demaine, E. D.; Fomin, F. V.; Hajiaghayi, M.; Thilikos, D. M., Bidimensional parameters and local treewidth, SIAM J. Discrete Math., 18, 501-511 (2005) · Zbl 1069.05070 |
| [3] | Demaine, E. D.; Fomin, F. V.; Hajiaghayi, M.; Thilikos, D. M., Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs, J. ACM, 52, 866-893 (2005) · Zbl 1326.05152 |
| [4] | Demaine, E. D.; Hajiaghayi, M., Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality, (Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005 (2005), SIAM), 682-689 · Zbl 1297.05227 |
| [5] | Demaine, E. D.; Hajiaghayi, M., The bidimensionality theory and its algorithmic applications, Comput. J., 51, 292-302 (2007) |
| [6] | Demaine, E. D.; Hajiaghayi, M., Linearity of grid minors in treewidth with applications through bidimensionality, Combinatorica, 28, 19-36 (2008) · Zbl 1174.05115 |
| [7] | Demaine, E. D.; Hajiaghayi, M.; Kawarabayashi, K., Algorithmic graph minor theory: Decomposition, approximation, and coloring, (Proceedings of the 46th Annual Symposium on Foundations of Computer Science. Proceedings of the 46th Annual Symposium on Foundations of Computer Science, FOCS 2005 (2005), IEEE Comput. Soc.), 637-646 |
| [8] | Demaine, E. D.; Hajiaghayi, M.; Thilikos, D. M., The bidimensional theory of bounded-genus graphs, SIAM J. Discrete Math., 20, 357-371 (2006) · Zbl 1117.05100 |
| [9] | Diestel, R.; Jensen, T. R.; Gorbunov, K. Y.; Thomassen, C., Highly connected sets and the excluded grid theorem, J. Combin. Theory Ser. B, 75, 61-73 (1999) · Zbl 0949.05075 |
| [10] | Feige, U.; Hajiaghayi, M. T.; Lee, J. R., Improved approximation algorithms for minimum-weight vertex separators, SIAM J. Comput., 38, 2, 629-657 (2008) · Zbl 1172.68063 |
| [11] | Fomin, F. V.; Golovach, P.; Thilikos, D. M., Contraction bidimensionality: The accurate picture, (Proceedings of the 17th Annual European Symposium on Algorithms. Proceedings of the 17th Annual European Symposium on Algorithms, ESA 2009. Proceedings of the 17th Annual European Symposium on Algorithms. Proceedings of the 17th Annual European Symposium on Algorithms, ESA 2009, Lecture Notes in Comput. Sci., vol. 5757 (2009), Springer-Verlag), 706-717 · Zbl 1256.05202 |
| [12] | Fomin, F. V.; Golovach, P.; Thilikos, D. M., Approximation algorithms for domination search, (Proceedings of 8th Workshop on Approximation and Online Algorithms. Proceedings of 8th Workshop on Approximation and Online Algorithms, WAOA 2010. Proceedings of 8th Workshop on Approximation and Online Algorithms. Proceedings of 8th Workshop on Approximation and Online Algorithms, WAOA 2010, Lecture Notes in Comput. Sci., vol. 6534 (2010), Springer-Verlag), 130-141 · Zbl 1314.68396 |
| [13] | Fomin, F. V.; Lokshtanov, D.; Raman, V.; Saurabh, S., Bidimensionality and EPTAS, (Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 (2011), ACM-SIAM), 748-759 · Zbl 1377.68324 |
| [14] | Fomin, F. V.; Lokshtanov, D.; Saurabh, S.; Thilikos, D. M., Bidimensionality and kernels, (Proceedings of 21st Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010 (2010), SIAM), 503-510 · Zbl 1288.68116 |
| [15] | Geelen, J. F.; Richter, R. B.; Salazar, G., Embedding grids in surfaces, European J. Combin., 25, 785-792 (2004) · Zbl 1050.05035 |
| [16] | Mohar, B., Combinatorial local planarity and the width of graph embeddings, Canad. J. Math., 44, 1272-1288 (1992) · Zbl 0777.05052 |
| [17] | Mohar, B.; Thomassen, C., Graphs on Surfaces (2001), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 0979.05002 |
| [18] | Robertson, N.; Seymour, P. D., Graph minors. V. Excluding a planar graph, J. Combin. Theory Ser. B, 41, 92-114 (1986) · Zbl 0598.05055 |
| [19] | Robertson, N.; Seymour, P. D., Graph minors. X. Obstructions to tree-decomposition, J. Combin. Theory Ser. B, 52, 153-190 (1991) · Zbl 0764.05069 |
| [20] | Robertson, N.; Seymour, P. D., Graph minors. XVI. Excluding a non-planar graph, J. Combin. Theory Ser. B, 89, 43-76 (2003) · Zbl 1023.05040 |
| [21] | Robertson, N.; Seymour, P.; Thomas, R., Quickly excluding a planar graph, J. Combin. Theory Ser. B, 62, 323-348 (1994) · Zbl 0807.05023 |
| [22] | Thomassen, C., A simpler proof of the excluded minor theorem for higher surfaces, J. Combin. Theory Ser. B, 70, 306-311 (1997) · Zbl 0882.05053 |
| [23] | P. van ʼt Hof, M. Kaminski, D. Paulusma, S. Szeider, D.M. Thilikos, On graph contractions and induced minors, Discrete Appl. Math., in press, doi:10.1016/j.dam.2010.05.005; P. van ʼt Hof, M. Kaminski, D. Paulusma, S. Szeider, D.M. Thilikos, On graph contractions and induced minors, Discrete Appl. Math., in press, doi:10.1016/j.dam.2010.05.005 · Zbl 1241.05137 |
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.
