Elimination distance to bounded degree on planar graphs

• Autorzy: Lindermayr, Alexander , Siebertz, Sebastian , Vigny, Alexandre
• Języki publikacji: EN

Abstrakty

EN

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, k decides in time f(k, d) · nc 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.

Słowa kluczowe

EN

computer science; discrete mathematics; mathematics - combinatorics

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2024
• Tom: Vol. 191, nr 2
• Strony: 129--140
• Opis fizyczny: Bibliogr. 28 poz., rys.

Twórcy

autor

Lindermayr, Alexander

• University of Bremen Germany,

autor

Siebertz, Sebastian

• University of Bremen Germany,

autor

Vigny, Alexandre

• University of Bremen Germany,

Bibliografia

• [1] Guo J, Hüffner F, Niedermeier R. A structural view on parameterizing problems: Distance from triviality. In: Parameterized and Exact Computation, First Intl. Workshop (IWPEC). Springer, 2004 pp. 162-173. doi:10.1007/978-3-540-28639-4 15.
• [2] Gajarský J, Hlinený P, Obdrzálek J, Ordyniak S, Reidl F, Rossmanith P, Villaamil FS, Sikdar S. Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci., 2017. 84:219-242. doi:10.1016/j.jcss.2016.09.002.
• [3] Bulian J, Dawar A. Graph isomorphism parameterized by elimination distance to bounded degree. Algo-rithmica, 2016. 75(2):363-382. doi:10.1007/s00453-015-0045-3.
• [4] Hols EC, Kratsch S, Pieterse A. Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. SIAM J. Discret. Math., 2022. 36(3):1955-1990. doi:10.1137/20M1335285.
• [5] Dreier J, Ordyniak S, Szeider S. SAT backdoors: Depth beats size. Journal of Computer and System Sciences, 2024. 142:103520. doi:10.1016/j.jcss.2024.103520.
• [6] Mӓhlmann N, Siebertz S, Vigny A. Recursive Backdoors for SAT. In: Intl. Symp. on Mathematical Foundations of Computer Science (MFCS), volume 202 of LIPIcs. 2021 pp. 73:1-73:18. doi:10.48550/ arXiv.2102.04707.
• [7] Bodlaender HL, Deogun JS, Jansen K, Kloks T, Kratsch D, Mu¨ller H, Tuza Z. Rankings of graphs. SIAM J. Discret. Math., 1998. 11(1):168-181.
• [8] Nešetřil J, De Mendez PO. Sparsity: graphs, structures, and algorithms, volume 28. Springer Science & Business Media, 2012. doi:10.1007/978-3-642-27875-4.
• [9] Reidl F, Rossmanith P, Villaamil FS, Sikdar S. A Faster Parameterized Algorithm for Treedepth. In: Intl. Coll. on Automata, Languages and Programming (ICALP), volume 8572 of Lecture Notes in Computer Science. 2014 pp. 931-942. doi:10.1007/978-3-662-43948-7 77.
• [10] Bulian J, Dawar A. Fixed-parameter tractable distances to sparse graph classes. Algorithmica, 2017. 79(1):139-158. doi:10.1007/s00453-016-0235-7.
• [11] Courcelle B. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and computation, 1990. 85(1):12-75. doi:10.1016/0890-5401(90)90043-H.
• [12] Dvořrák Z, Král D, Thomas R. Testing first-order properties for subclasses of sparse graphs. Journal of the ACM (JACM), 2013. 60(5):36. doi:10.1145/2499483.
• [13] Grohe M, Kreutzer S, Siebertz S. Deciding first-order properties of nowhere dense graphs. Journal of the ACM (JACM), 2017. 64(3):17. doi:10.1145/3051095.
• [14] Robertson N, Seymour PD. Graph minors. V. Excluding a planar graph. J. Comb. Theory Ser. B, 1986. 41(1):92-114.
• [15] Robertson N, Seymour P. Graph Minors. XIII. The Disjoint Paths Problem. J. Comb. Theory Ser. B, 1995. 63(1):65-110. doi:10.1006/jctb.1995.1006.
• [16] Thilikos DM. Graph minors and parameterized algorithm design. In: The Multivariate Algorithmic Revolution and Beyond, Springer, 2012 pp. 228-256. doi:10.1007/978-3-642-30891-8 13.
• [17] Lindermayr A, Siebertz S, Vigny A. Elimination Distance to Bounded Degree on Planar Graphs. In: Intl. Symp. on Mathematical Foundations of Computer Science (MFCS), volume 170 of LIPIcs. 2020 pp. 65:1-65:12. doi:10.48550/arXiv.2007.02413.
• [18] Agrawal A, Kanesh L, Panolan F, Ramanujan MS, Saurabh S. A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs. SIAM J. Discret. Math., 2022. 36(2):911-921. doi:10.1137/21M1396824.
• [19] Agrawal A, Kanesh L, Lokshtanov D, Panolan F, Ramanujan MS, Saurabh S. Elimination Distance to Topological-minor-free Graphs is FPT. CoRR, 2021. abs/2104.09950.
• [20] Agrawal A, Ramanujan MS. On the Parameterized Complexity of Clique Elimination Distance. In: Intl. Symp. on Parameterized and Exact Computation (IPEC), volume 180 of LIPIcs. 2020 pp. 1:1-1:13.
• [21] Diner O¨ Y, Giannopoulou AC, Stamoulis G, Thilikos DM. Block Elimination Distance. Graphs Comb., 2022. 38(5):133. doi:10.1007/s00373-022-02513-y.
• [22] Fomin FV, Golovach PA, Thilikos DM. Parameterized Complexity of Elimination Distance to First-Order Logic Properties. ACM Trans. Comput. Log., 2022. 23(3):17:1-17:35. doi:10.1145/3517129.
• [23] Pilipczuk M, Schirrmacher N, Siebertz S, Torunczyk S, Vigny A. Algorithms and Data Structures for First-Order Logic with Connectivity Under Vertex Failures. In: Intl. Coll. on Automata, Languages and Pro-gramming (ICALP), volume 229 of LIPIcs. 2022 pp. 102:1-102:18. doi:10.4230/LIPIcs.ICALP.2022.102.
• [24] Schirrmacher N, Siebertz S, Vigny A. First-order Logic with Connectivity Operators. ACM Trans. Comput. Log., 2023. 24(30):1-23. doi:10.1145/3595922.
• [25] Bulian J. Parameterized complexity of distances to sparse graph classes. Technical report, University of Cambridge, Computer Laboratory, 2017. doi:10.48456/tr-902.
• [26] Chuzhoy J, Tan Z. Towards tight(er) bounds for the Excluded Grid Theorem. J. Comb. Theory, Ser. B, 2021. 146:219-265. doi:10.1016/j.jctb.2020.09.010.
• [27] Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S. Parame-terized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
• [28] Libkin L. Elements of finite model theory. Springer Science & Business Media, 2013. ISBN:3540212027, 9783540212027.

Identyfikatory

DOI

10.3233/FI-242175