Document Open Access Logo

Elimination Distance to Bounded Degree on Planar Graphs

Authors Alexander Lindermayr , Sebastian Siebertz , Alexandre Vigny

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.65.pdf
  • Filesize: 478 kB
  • 12 pages

Document Identifiers

Author Details

Alexander Lindermayr
  • University of Bremen, Germany
Sebastian Siebertz
  • University of Bremen, Germany
Alexandre Vigny
  • University of Bremen, Germany

Cite AsGet BibTex

Alexander Lindermayr, Sebastian Siebertz, and Alexandre Vigny. Elimination Distance to Bounded Degree on Planar Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 65:1-65:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.65

Abstract

We study the graph parameter elimination distance to bounded degree, which was introduced by Bulian and Dawar in their study of the parameterized complexity of the graph isomorphism problem. We prove that the problem is fixed-parameter tractable on planar graphs, that is, there exists an algorithm that given a planar graph G and integers d and k decides in time f(k,d)⋅ n^c for a computable function f and constant c whether the elimination distance of G to the class of degree d graphs is at most k.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Fixed parameter tractability
Keywords
  • Elimination distance
  • parameterized complexity
  • structural graph theory

Metrics

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

Related Versions

References

  1. Hans L Bodlaender, Jitender S Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko Müller, and Zsolt Tuza. Rankings of graphs. SIAM Journal on Discrete Mathematics, 11(1):168-181, 1998. Google Scholar
  2. Jannis Bulian. Parameterized complexity of distances to sparse graph classes. Technical report, University of Cambridge, Computer Laboratory, 2017. Google Scholar
  3. Jannis Bulian and Anuj Dawar. Graph isomorphism parameterized by elimination distance to bounded degree. Algorithmica, 75(2):363-382, 2016. Google Scholar
  4. Jannis Bulian and Anuj Dawar. Fixed-parameter tractable distances to sparse graph classes. Algorithmica, 79(1):139-158, 2017. Google Scholar
  5. Julia Chuzhoy and Zihan Tan. Towards tight (er) bounds for the excluded grid theorem. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1445-1464. SIAM, 2019. Google Scholar
  6. Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Information and computation, 85(1):12-75, 1990. Google Scholar
  7. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  8. Zdeněk Dvořák, Daniel Král, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. Journal of the ACM (JACM), 60(5):36, 2013. Google Scholar
  9. Jakub Gajarský, Petr Hliněný, Jan Obdržálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. Kernelization using structural parameters on sparse graph classes. Journal of Computer and System Sciences, 84:219-242, 2017. Google Scholar
  10. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. Journal of the ACM (JACM), 64(3):17, 2017. Google Scholar
  11. Jiong Guo, Falk Hüffner, and Rolf Niedermeier. A structural view on parameterizing problems: Distance from triviality. In International Workshop on Parameterized and Exact Computation, pages 162-173. Springer, 2004. Google Scholar
  12. Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse. Elimination distances, blocking sets, and kernels for vertex cover. In STACS, 2020. Google Scholar
  13. Leonid Libkin. Elements of finite model theory. Springer Science & Business Media, 2013. Google Scholar
  14. Jaroslav Nešetřil and Patrice Ossona De Mendez. Sparsity: graphs, structures, and algorithms, volume 28. Springer Science & Business Media, 2012. Google Scholar
  15. Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. A faster parameterized algorithm for treedepth. In International Colloquium on Automata, Languages, and Programming, pages 931-942. Springer, 2014. Google Scholar
  16. Neil Robertson and Paul D Seymour. Graph minors. V. excluding a planar graph. Journal of Combinatorial Theory, Series B, 41(1):92-114, 1986. Google Scholar
  17. Neil Robertson and PD Seymour. Graph minors. XIII. the disjoint paths problem. J. Combin. Theory Ser. B, 63:65-110, 1995. Google Scholar
  18. Dimitrios M Thilikos. Graph minors and parameterized algorithm design. In The Multivariate Algorithmic Revolution and Beyond, pages 228-256. Springer, 2012. Google Scholar
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