Document Open Access Logo

Kernelization of Whitney Switches

Authors Fedor V. Fomin , Petr A. Golovach

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.48.pdf
  • Filesize: 0.72 MB
  • 19 pages

Document Identifiers

Author Details

Fedor V. Fomin
  • Department of Informatics, University of Bergen, Norway
Petr A. Golovach
  • Department of Informatics, University of Bergen, Norway

Funding

The research leading to these results has received funding from the Research Council of Norway via the project "MULTIVAL" (grant no. 263317).

Acknowledgements

We are grateful to Erlend Raa Vågset for fruitful discussions that initiated the research resulted in the paper.

Cite AsGet BibTex

Fedor V. Fomin and Petr A. Golovach. Kernelization of Whitney Switches. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 48:1-48:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.48

Abstract

A fundamental theorem of Whitney from 1933 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 𝒪(k), and thus, is fixed-parameter tractable when parameterized by k.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Whitney switch
  • 2-isomorphism
  • Parameterized Complexity
  • kernelization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings 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. URL: https://doi.org/10.1145/2897518.2897542.
  2. 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. URL: https://doi.org/10.1007/3-540-45749-6_21.
  3. Piotr Berman and Marek Karpinski. On some tighter inapproximability results (extended abstract). In Automata, Languages and Programming, 26th International Colloquium, ICALP'99, Prague, Czech Republic, July 11-15, 1999, Proceedings, volume 1644 of Lecture Notes in Computer Science, pages 200-209. Springer, 1999. URL: https://doi.org/10.1007/3-540-48523-6_17.
  4. Prosenjit Bose and Ferran Hurtado. Flips in planar graphs. Comput. Geom., 42(1):60-80, 2009. URL: https://doi.org/10.1016/j.comgeo.2008.04.001.
  5. 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. URL: https://doi.org/10.1016/j.jda.2016.05.002.
  6. 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.
  7. Alberto Caprara. Sorting by reversals is difficult. In Proceedings of the First Annual International Conference on Research in Computational Molecular Biology, RECOMB 1997, Santa Fe, NM, USA, January 20-23, 1997, pages 75-83. ACM, 1997. URL: https://doi.org/10.1145/267521.267531.
  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. URL: https://doi.org/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. URL: https://doi.org/10.1137/S0895480197331995.
  10. Sean Cleary and Katherine St. John. Rotation distance is fixed-parameter tractable. Inform. Process. Lett., 109(16):918-922, 2009. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/10.1007/978-3-319-21275-3.
  13. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  14. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  15. Fedor V. Fomin and Petr A. Golovach. Kernelization of whitney switches. CoRR, abs/2006.13684, 2020. URL: http://arxiv.org/abs/2006.13684.
  16. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization. Cambridge University Press, Cambridge, 2019. Theory of parameterized preprocessing. Google Scholar
  17. 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. 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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. Google Scholar
  22. Anna Lubiw and Vinayak Pathak. Flip distance between two triangulations of a point set is NP-complete. Comput. Geom., 49:17-23, 2015. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/10.1007/s00453-016-0159-2.
  25. Pavel A. Pevzner. Computational molecular biology - an algorithmic approach. MIT Press, 2000. Google Scholar
  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. URL: https://doi.org/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. URL: https://doi.org/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. Google Scholar
  29. Klaus Truemper. On whitney’s 2-isomorphism theorem for graphs. Journal of Graph Theory, 4(1):43-49, 1980. URL: https://doi.org/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. Google Scholar
  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. Google Scholar
  32. Dirk L. Vertigan and Geoffrey P. Whittle. A 2-isomorphism theorem for hypergraphs. J. Comb. Theory, Ser. B, 71(2):215-230, 1997. URL: https://doi.org/10.1006/jctb.1997.1789.
  33. Fabian Wagner. Hardness results for tournament isomorphism and automorphism. In Mathematical 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. URL: https://doi.org/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. URL: https://doi.org/10.2307/1989545.
  35. Hassler Whitney. 2-Isomorphic Graphs. Amer. J. Math., 55(1-4):245-254, 1933. URL: https://doi.org/10.2307/2371127.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact