Kernelization of Whitney switches. (English) Zbl 07651187
Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 48, 19 p. (2020).
Summary: A fundamental theorem by [H. Whitney, Am. J. Math. 55, 245–254 (1933; Zbl 0006.37005); Am. J. Math. 55, 245–254 (1933; JFM 59.1235.01)] asserts that 2-connected graphs \(G\) and \(H\) are \(2\)-isomorphic, or equivalently, their cycle matroids are isomorphic, if and only if \(G\) can be transformed into \(H\) by a series of operations called Whitney switches. In this paper we consider the quantitative question arising from Whitney’s theorem: Given \(2\)-isomorphic graphs, can we transform one into another by applying at most \(k\) Whitney switches? This problem is already NP-complete for cycles, and we investigate its parameterized complexity. We show that the problem admits a kernel of size \(\mathcal{O}(k)\), and thus, is fixed-parameter tractable when parameterized by \(k\).
For the entire collection see [Zbl 1445.68017].
For the entire collection see [Zbl 1445.68017].
MSC:
| 68Wxx | Algorithms in computer science |
References:
| [1] | László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. |
| [2] | In Proceed-ings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 684-697. ACM, 2016. doi:10.1145/2897518. 2897542. · Zbl 1376.68058 · doi:10.1145/2897518.2897542 |
| [3] | Piotr Berman, Sridhar Hannenhalli, and Marek Karpinski. 1.375-approximation algorithm for sorting by reversals. In Algorithms -ESA 2002, 10th Annual European Symposium, Rome, Italy, September 17-21, 2002, Proceedings, volume 2461 of Lecture Notes in Computer Science, pages 200-210. Springer, 2002. doi:10.1007/3-540-45749-6_21. · Zbl 1019.68817 · doi:10.1007/3-540-45749-6_21 |
| [4] | Piotr Berman and Marek Karpinski. On some tighter inapproximability results (extended abstract). In Automata, Languages and Programming, 26th International Colloquium, IC-ALP’99, Prague, Czech Republic, July 11-15, 1999, Proceedings, volume 1644 of Lecture Notes in Computer Science, pages 200-209. Springer, 1999. doi:10.1007/3-540-48523-6_17. · doi:10.1007/3-540-48523-6_17 |
| [5] | Prosenjit Bose and Ferran Hurtado. Flips in planar graphs. Comput. Geom., 42(1):60-80, 2009. doi:10.1016/j.comgeo.2008.04.001. · Zbl 1146.05016 · doi:10.1016/j.comgeo.2008.04.001 |
| [6] | Laurent Bulteau, Guillaume Fertin, and Christian Komusiewicz. (Prefix) reversal distance for (signed) strings with few blocks or small alphabets. J. Discrete Algorithms, 37:44-55, 2016. doi:10.1016/j.jda.2016.05.002. · Zbl 1362.68300 · doi:10.1016/j.jda.2016.05.002 |
| [7] | Laurent Bulteau, Falk Hüffner, Christian Komusiewicz, and Rolf Niedermeier. Multivariate algorithmics for NP-hard string problems. Bulletin of the EATCS, 114, 2014. URL: http: //eatcs.org/beatcs/index.php/beatcs/article/view/310. · Zbl 1409.68350 |
| [8] | Markus Chimani, Petr Hlinený, and Petra Mutzel. Vertex insertion approximates the crossing number of apex graphs. Eur. J. Comb., 33(3):326-335, 2012. doi:10.1016/j.ejc.2011.09. 009. · Zbl 1230.05267 · doi:10.1016/j.ejc.2011.09.009 |
| [9] | David A. Christie and Robert W. Irving. Sorting strings by reversals and by transpositions. SIAM J. Discrete Math., 14(2):193-206, 2001. doi:10.1137/S0895480197331995. · Zbl 0968.68116 · doi:10.1137/S0895480197331995 |
| [10] | Sean Cleary and Katherine St. John. Rotation distance is fixed-parameter tractable. Inform. Process. Lett., 109(16):918-922, 2009. doi:10.1016/j.ipl.2009.04.023. · Zbl 1205.68531 · doi:10.1016/j.ipl.2009.04.023 |
| [11] | Bruno Courcelle. The monadic second-order logic of graphs XI: hierarchical decompositions of connected graphs. Theor. Comput. Sci., 224(1-2):35-58, 1999. doi:10.1016/S0304-3975(98) 00306-5. · Zbl 0938.03015 · doi:10.1016/S0304-3975(98)00306-5 |
| [12] | Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3. · Zbl 1334.90001 · doi:10.1007/978-3-319-21275-3 |
| [13] | Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. |
| [14] | Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. doi:10.1007/978-1-4471-5559-1. · Zbl 1358.68006 · doi:10.1007/978-1-4471-5559-1 |
| [15] | Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization. Cambridge University Press, Cambridge, 2019. Theory of parameterized preprocessing. · Zbl 1426.68003 |
| [16] | Sridhar Hannenhalli and Pavel A. Pevzner. To cut... or not to cut (applications of comparative physical maps in molecular evolution). In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 28-30 January 1996, Atlanta, Georgia, USA, pages 304-313. · Zbl 0852.68119 |
| [17] | ACM/SIAM, 1996. URL: http://dl.acm.org/citation.cfm?id=313852.314077. |
| [18] | John E. Hopcroft and Robert Endre Tarjan. Dividing a graph into triconnected components. SIAM J. Comput., 2(3):135-158, 1973. doi:10.1137/0202012. · Zbl 0281.05111 · doi:10.1137/0202012 |
| [19] | Iyad A. Kanj, Eric Sedgwick, and Ge Xia. Computing the flip distance between triangulations. Discrete & Computational Geometry, 58(2):313-344, 2017. doi:10.1007/s00454-017-9867-x. · Zbl 1371.05063 · doi:10.1007/s00454-017-9867-x |
| [20] | John D. Kececioglu and David Sankoff. Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement. Algorithmica, 13(1/2):180-210, 1995. doi:10.1007/BF01188586. · Zbl 0831.92014 · doi:10.1007/BF01188586 |
| [21] | Daniel Lokshtanov, Amer E Mouawad, Fahad Panolan, MS Ramanujan, and Saket Saurabh. Reconfiguration on sparse graphs. Journal of Computer and System Sciences, 95:122-131, 2018. · Zbl 1390.68351 |
| [22] | Anna Lubiw and Vinayak Pathak. Flip distance between two triangulations of a point set is NP-complete. Comput. Geom., 49:17-23, 2015. doi:10.1016/j.comgeo.2014.11.001. · Zbl 1333.65022 · doi:10.1016/j.comgeo.2014.11.001 |
| [23] | Joan M. Lucas. An improved kernel size for rotation distance in binary trees. Inform. Process. Lett., 110(12-13):481-484, 2010. doi:10.1016/j.ipl.2010.04.022. · Zbl 1233.68147 · doi:10.1016/j.ipl.2010.04.022 |
| [24] | Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour, and Akira Suzuki. On the parameterized complexity of reconfiguration problems. Algorithmica, 78(1):274-297, 2017. doi:10.1007/s00453-016-0159-2. · Zbl 1360.68516 · doi:10.1007/s00453-016-0159-2 |
| [25] | Pavel A. Pevzner. Computational molecular biology -an algorithmic approach. MIT Press, 2000. · Zbl 0972.92011 |
| [26] | Pascal Schweitzer. A polynomial-time randomized reduction from tournament isomorphism to tournament asymmetry. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 66:1-66:14. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs. ICALP.2017.66. · Zbl 1441.68196 · doi:10.4230/LIPIcs.ICALP.2017.66 |
| [27] | Andrew Solomon, Paul J. Sutcliffe, and Raymond Lister. Sorting circular permutations by reversal. In Algorithms and Data Structures, 8th International Workshop, WADS 2003, Ottawa, Ontario, Canada, July 30 -August 1, 2003, Proceedings, volume 2748 of Lecture Notes in Computer Science, pages 319-328. Springer, 2003. doi:10.1007/978-3-540-45078-8_28. · Zbl 1278.68227 · doi:10.1007/978-3-540-45078-8_28 |
| [28] | Carsten Thomassen. Embeddings and minors. In Handbook of combinatorics, Vol. 1, 2, pages 301-349. Elsevier Sci. B. V., Amsterdam, 1995. · Zbl 0851.05043 |
| [29] | Klaus Truemper. On whitney’s 2-isomorphism theorem for graphs. Journal of Graph Theory, 4(1):43-49, 1980. doi:10.1002/jgt.3190040106. · Zbl 0397.05043 · doi:10.1002/jgt.3190040106 |
| [30] | W. T. Tutte. Connectivity in graphs. Mathematical Expositions, No. 15. University of Toronto Press, Toronto, Ont.; Oxford University Press, London, 1966. · Zbl 0146.45603 |
| [31] | W. T. Tutte. Graph theory, volume 21 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2001. With a foreword by Crispin St. J. A. Nash-Williams, Reprint of the 1984 original. · Zbl 0964.05001 |
| [32] | Dirk L. Vertigan and Geoffrey P. Whittle. A 2-isomorphism theorem for hypergraphs. J. Comb. Theory, Ser. B, 71(2):215-230, 1997. doi:10.1006/jctb.1997.1789. · Zbl 0888.05045 · doi:10.1006/jctb.1997.1789 |
| [33] | Fabian Wagner. Hardness results for tournament isomorphism and automorphism. In Math-ematical Foundations of Computer Science 2007, 32nd International Symposium, MFCS 2007, Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings, volume 4708 of Lecture Notes in Computer Science, pages 572-583. Springer, 2007. doi:10.1007/978-3-540-74456-6_51. · Zbl 1147.05305 · doi:10.1007/978-3-540-74456-6_51 |
| [34] | Hassler Whitney. Non-separable and planar graphs. Trans. Amer. Math. Soc., 34(2):339-362, 1932. doi:10.2307/1989545. · JFM 58.0608.01 · doi:10.2307/1989545 |
| [35] | Hassler Whitney. 2-Isomorphic Graphs. Amer. J. Math., 55(1-4):245-254, 1933. doi:10.2307/ 2371127. · JFM 59.1235.01 · doi:10.2307/2371127 |
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.
