Document Open Access Logo

Compound Logics for Modification Problems

Authors Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.61.pdf
  • Filesize: 0.95 MB
  • 21 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
Ignasi Sau
  • LIRMM, Université de Montpellier, CNRS, France
Giannos Stamoulis
  • LIRMM, Université de Montpellier, CNRS, France
Dimitrios M. Thilikos
  • LIRMM, Université de Montpellier, CNRS, France

Funding

  • Fomin, Fedor V.: Supported by the Research Council of Norway via the project BWCA (grant no. 314528).
  • Golovach, Petr A.: Supported by the Research Council of Norway via the project BWCA (grant no. 314528).
  • Sau, Ignasi: Supported by the ANR projects ELIT (ANR-20-CE48-0008-01) and ESIGMA (ANR-17-CE23-0010) and the French-German Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027).
  • Stamoulis, Giannos: Supported by the ANR project ESIGMA (ANR-17-CE23-0010) and the French-German Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027).
  • Thilikos, Dimitrios M.: Supported by the ANR project ESIGMA (ANR-17-CE23-0010) and the French-German Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027).

Acknowledgements

We wish to thank the anonymous reviewers for their valuable remarks.

Cite As Get BibTex

Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Compound Logics for Modification Problems. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 61:1-61:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.61

Abstract

We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence, defining some property of the modified part of the graph, and the target sentence, defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic (CMSOL) and have models of bounded treewidth, while target sentences express first-order logic (FOL) properties along with minor-exclusion. Our logic captures problems that are not definable in first-order logic and, moreover, may have instances of unbounded treewidth. Also, it permits the modeling of wide families of problems involving vertex/edge removals, alternative modulator measures (such as elimination distance or G-treewidth), multistage modifications, and various cut problems. Our main result is that, for this compound logic, model-checking can be done in quadratic time. All derived algorithms are constructive and this, as a byproduct, extends the constructibility horizon of the algorithmic applications of the Graph Minors theorem of Robertson and Seymour. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique. It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle’s theorem does not apply.

Subject Classification

ACM Subject Classification
  • Theory of computation → Logic
  • Theory of computation → Parameterized complexity and exact algorithms
  • Mathematics of computing → Graph algorithms
Keywords
  • Algorithmic meta-theorems
  • Graph modification problems
  • Model-checking
  • Graph minors
  • First-order logic
  • Monadic second-order logic
  • Flat Wall theorem
  • Irrelevant vertex technique

Metrics

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

Related Versions

References

  1. Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent. In Proc. of the 32st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1976-2004, 2022. URL: https://doi.org/10.1137/1.9781611977073.79.
  2. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12:308-340, 1991. URL: https://doi.org/10.1016/0196-6774(91)90006-K.
  3. Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary. In Proc. of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 951-970, 2020. URL: https://doi.org/10.1137/1.9781611975994.57.
  4. Hans L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. In Proc. of the 25th Annual ACM Symposium on Theory of Computing (STOC), pages 226-234, 1993. URL: https://doi.org/10.1145/167088.167161.
  5. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (Meta) Kernelization. Journal of the ACM, 63(5):44:1-44:69, 2016. URL: https://doi.org/10.1145/2973749.
  6. Mikołaj Bojańczyk. Separator logic and star-free expressions for graphs, 2021. URL: https://arxiv.org/abs/2107.13953.
  7. Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, and Szymon Torunczyk. Model checking on interpretations of classes of bounded local cliquewidth. In Proc. of the 37th Annual ACM/IEEE Symposium on Logic in Computer (LICS), pages 54:1-54:13. ACM, 2022. URL: https://doi.org/10.1145/3531130.3533367.
  8. Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Torunczyk. Twin-width IV: ordered graphs and matrices. In Proc. of the 54th Annual ACM Symposium on Theory of Computing (STOC). ACM, 2022. URL: https://doi.org/10.1145/3519935.3520037.
  9. Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking. In Proc. of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 601-612, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00062.
  10. Richard B. Borie, R. Gary Parker, and Craig A. Tovey. Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica, 7(5-6):555-581, 1992. URL: https://doi.org/10.1007/BF01758777.
  11. Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau. Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel. In Proc. of the 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168 of LIPIcs, pages 16:1-16:19, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.16.
  12. Jannis Bulian and Anuj Dawar. Fixed-parameter tractable distances to sparse graph classes. Algorithmica, 79(1):139-158, 2017. URL: https://doi.org/10.1007/s00453-016-0235-7.
  13. Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger. Improved algorithms for feedback vertex set problems. Journal of Computer and System Sciences, 74(7):1188-1198, 2008. URL: https://doi.org/10.1016/j.jcss.2008.05.002.
  14. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved parameterized upper bounds for vertex cover. In Proc. of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 4162 of LNCS, pages 238-249, 2006. URL: https://doi.org/10.1007/11821069_21.
  15. Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Information and Computation, 85(1):12-75, 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-H.
  16. Bruno Courcelle. The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues. RAIRO - Theoretical Informatics and Applications, 26:257-286, 1992. URL: https://doi.org/10.1051/ita/1992260302571.
  17. Bruno Courcelle. The expression of graph properties and graph transformations in monadic second-order logic. In Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations, pages 313-400. World Scientific, 1997. Google Scholar
  18. Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2012. Google Scholar
  19. Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems, 33(2):125-150, 2000. URL: https://doi.org/10.1007/s002249910009.
  20. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  21. Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Minimum bisection is fixed-parameter tractable. SIAM Journal on Computing, 48(2):417-450, 2019. URL: https://doi.org/10.1137/140988553.
  22. Marek Cygan, Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk. Hitting forbidden subgraphs in graphs of bounded treewidth. Information and Computation, 256:62-82, 2017. URL: https://doi.org/10.1016/j.ic.2017.04.009.
  23. Anuj Dawar, Martin Grohe, and Stephan Kreutzer. Locally excluding a minor. In Proc. of the 21st IEEE Symposium on Logic in Computer Science (LICS), pages 270-279, 2007. URL: https://doi.org/10.1109/LICS.2007.31.
  24. Oznur Y. Diner, Archontia C. Giannopoulou, Giannos Stamoulis, and Dimitrios M. Thilikos. Block elimination distance. In Proc. of the 50th International Workshop on Graph Theoretic Concepts in Computer Science (WG), volume 12911 of LNCS, 2002. URL: https://doi.org/10.1007/978-3-030-86838-3_3.
  25. Jan Dreier and Peter Rossmanith. Approximate evaluation of first-order counting queries. In Dániel Marx, editor, Proc. of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1720-1739. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.104.
  26. Zdeněk Dvořák, Daniel Král, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. Journal of the ACM, 60(5):36:1-36:24, 2013. URL: https://doi.org/10.1145/2499483.
  27. Eduard Eiben, Robert Ganian, Thekla Hamm, and O-joung Kwon. Measuring what matters: A hybrid approach to dynamic programming with treewidth. Journal of Computer and System Sciences, 121:57-75, 2021. URL: https://doi.org/10.1016/j.jcss.2021.04.005.
  28. Michael R. Fellows and Michael A. Langston. Nonconstructive tools for proving polynomial-time decidability. Journal of the ACM, 35(3):727-739, 1988. URL: https://doi.org/10.1145/44483.44491.
  29. Samuel Fiorini, Nadia Hardy, Bruce A. Reed, and Adrian Vetta. Planar graph bipartization in linear time. Discrete Applied Mathematics, 156(7):1175-1180, 2008. URL: https://doi.org/10.1016/j.dam.2007.08.013.
  30. Jörg Flum and Martin Grohe. Fixed-parameter tractability, definability, and model-checking. SIAM Journal on Computing, 31(1):113-145, 2001. URL: https://doi.org/10.1137/S0097539799360768.
  31. Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Compound logics for modification problems, 2021. URL: https://arxiv.org/abs/2111.02755.
  32. Fedor V. Fomin, Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. An algorithmic meta-theorem for graph modification to planarity and FOL. In Proc. of the 28th Annual European Symposium on Algorithms (ESA), volume 173 of LIPIcs, pages 51:1-51:17, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.51.
  33. Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos. On the parameterized complexity of graph modification to first-order logic properties. Theory of Computing Systems, 64(2):251-271, 2020. URL: https://doi.org/10.1007/s00224-019-09938-8.
  34. Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos. Parameterized complexity of elimination distance to first-order logic properties. ACM Transactions on Computational Logic, 23(3):17:1-17:35, 2022. URL: https://doi.org/10.1145/3517129.
  35. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. In Proc. of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 470-479, 2012. URL: https://doi.org/10.1109/FOCS.2012.62.
  36. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Hitting topological minors is FPT. In Proc. of the 52nd Annual ACM Symposium on Theory of Computing (STOC), pages 1317-1326, 2020. URL: https://doi.org/10.1145/3357713.3384318.
  37. Markus Frick and Martin Grohe. Deciding first-order properties of locally tree-decomposable structures. Journal of the ACM, 48(6):1184-1206, 2001. URL: https://doi.org/10.1145/504794.504798.
  38. Haim Gaifman. On local and non-local properties. In Proc. of the Herbrand Symposium, volume 107 of Studies in Logic and the Foundations of Mathematics, pages 105-135. Elsevier, 1982. URL: https://doi.org/10.1016/S0049-237X(08)71879-2.
  39. Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, and Szymon Torunczyk. First-order interpretations of bounded expansion classes. ACM Transactions on Computational Logic, 21(4):29:1-29:41, 2020. URL: https://doi.org/10.1145/3382093.
  40. Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Linear kernels for edge deletion problems to immersion-closed graph classes. SIAM Journal on Discrete Mathematics, 35(1):105-151, 2021. URL: https://doi.org/10.1137/18M1228839.
  41. Petr A. Golovach, Dieter Kratsch, and Daniël Paulusma. Detecting induced minors in AT-free graphs. Theoretical Computer Science, 482:20-32, 2013. URL: https://doi.org/10.1016/j.tcs.2013.02.029.
  42. Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. Model-checking for first-order logic with disjoint paths predicates in proper minor-closed graph classes, 2022. URL: https://arxiv.org/abs/2211.01723.
  43. Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. Model-checking for first-order logic with disjoint paths predicates in proper minor-closed graph classes. In Proc. of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3684-3699, 2023. URL: https://doi.org/10.1137/1.9781611977554.ch141.
  44. Martin Grohe. Logic, graphs, and algorithms. In Logic and Automata: History and Perspectives, in Honor of Wolfgang Thomas, volume 2 of Texts in Logic and Games, pages 357-422. Amsterdam University Press, 2008. URL: https://eccc.weizmann.ac.il/report/2007/091/.
  45. Martin Grohe and Stephan Kreutzer. Methods for algorithmic meta theorems. In Model Theoretic Methods in Finite Combinatorics - AMS-ASL Joint Special Session, volume 558, pages 181-206. AMS, 2009. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.395.8282&rep=rep1&type=pdf.
  46. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. Journal of the ACM, 64(3):17:1-17:32, 2017. URL: https://doi.org/10.1145/3051095.
  47. Martin Grohe and Nicole Schweikardt. First-order query evaluation with cardinality conditions. In Proc. of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 253-266. ACM, 2018. URL: https://doi.org/10.1145/3196959.3196970.
  48. Jiong Guo, Falk Hüffner, and Rolf Niedermeier. A structural view on parameterizing problems: Distance from triviality. In Proc. of the 1st International Workshop on Parameterized and Exact Computation (IWPEC), volume 3162 of LNCS, pages 162-173, 2004. URL: https://doi.org/10.1007/978-3-540-28639-4_15.
  49. Bart M. P. Jansen, Jari J. H. de Kroon, and Michal Włodarczyk. Vertex deletion parameterized by elimination distance and even less. In Proc. of the 53rd Annual ACM Symposium on Theory of Computing (STOC), pages 1757-1769, 2021. URL: https://doi.org/10.1145/3406325.3451068.
  50. Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. A near-optimal planarization algorithm. In Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1802-1811, 2014. URL: https://doi.org/10.1137/1.9781611973402.130.
  51. Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce A. Reed. The disjoint paths problem in quadratic time. Journal of Combinatorial Theory, Series B, 102(2):424-435, 2012. URL: https://doi.org/10.1016/j.jctb.2011.07.004.
  52. Ken-ichi Kawarabayashi and Bruce A. Reed. Computing crossing number in linear time. In Proc. of the 39th annual ACM symposium on Theory of computing (STOC), pages 382-390, 2007. URL: https://doi.org/10.1145/1250790.1250848.
  53. Ken-ichi Kawarabayashi, Robin Thomas, and Paul Wollan. A new proof of the flat wall theorem. Journal of Combinatorial Theory, Series B, 129:204-238, 2018. URL: https://doi.org/10.1016/j.jctb.2017.09.006.
  54. Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Transactions on Algorithms, 12(2):21:1-21:41, 2016. URL: https://doi.org/10.1145/2797140.
  55. Tomasz Kociumaka and Marcin Pilipczuk. Deleting vertices to graphs of bounded genus. Algorithmica, 81(9):3655-3691, 2019. URL: https://doi.org/10.1007/s00453-019-00592-7.
  56. Tuukka Korhonen. A single-exponential time 2-approximation algorithm for treewidth. In Proc. of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 184-192, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00026.
  57. Stephan Kreutzer. On the parameterised intractability of monadic second-order logic. In Proc. of the 18th EACSL Annual Conference on Computer Science Logic (CSL), pages 348-363, 2009. URL: https://doi.org/10.1007/978-3-642-04027-6_26.
  58. Stephan Kreutzer. Algorithmic meta-theorems. In Finite and Algorithmic Model Theory, volume 379 of London Mathematical Society Lecture Note Series, pages 177-270. Cambridge University Press, 2011. URL: http://www.cs.ox.ac.uk/people/stephan.kreutzer/Publications/amt-survey.pdf.
  59. Dietrich Kuske and Nicole Schweikardt. First-order logic with counting. In Proc. of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-12. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/LICS.2017.8005133.
  60. John M. Lewis and Mihalis Yannakakis. The Node-Deletion Problem for Hereditary Properties is NP-Complete. Journal of Computer and System Sciences, 20(2):219-230, 1980. URL: https://doi.org/10.1016/0022-0000(80)90060-4.
  61. Dániel Marx and Igor Razgon. Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset. SIAM Journal on Computing, 43(2):355-388, 2014. URL: https://doi.org/10.1137/110855247.
  62. Dániel Marx and Ildikó Schlotter. Obtaining a planar graph by vertex deletion. Algorithmica, 62(3-4):807-822, 2012. URL: https://doi.org/10.1007/s00453-010-9484-z.
  63. Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27875-4.
  64. Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Rankwidth meets stability. In Proc. of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2014-2033. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.120.
  65. Jaroslav Nesetril, Patrice Ossona de Mendez, and Sebastian Siebertz. Structural properties of the first-order transduction quasiorder. In Proc. of the 30th EACSL Annual Conference on Computer Science Logic (CSL), volume 216 of LIPIcs, pages 31:1-31:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.CSL.2022.31.
  66. Michal Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Torunczyk, and Alexandre Vigny. Algorithms and data structures for first-order logic with connectivity under vertex failures. In Proc. of the 49th International Colloquium on Automata, Languages, and Programming, (ICALP), volume 229 of LIPIcs, pages 102:1-102:18, 2022. URL: https://doi.org/10.4230/LIPIcs.ICALP.2022.102.
  67. Neil Robertson and Paul D. Seymour. Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65-110, 1995. URL: https://doi.org/10.1006/jctb.1995.1006.
  68. Neil Robertson and Paul D. Seymour. Graph minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2):325-357, 2004. URL: https://doi.org/10.1016/j.jctb.2004.08.001.
  69. Ignasi Sau and Uéverton dos Santos Souza. Hitting forbidden induced subgraphs on bounded treewidth graphs. Information and Computation, 281:104812, 2021. URL: https://doi.org/10.1016/j.ic.2021.104812.
  70. Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes. In Proc. of the 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168 of LIPIcs, pages 95:1-95:20, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.95.
  71. Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. A more accurate view of the Flat Wall Theorem, 2021. URL: https://arxiv.org/abs/2102.06463.
  72. Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. k-apices of minor-closed graph classes. II. Parameterized algorithms. ACM Transactions on Algorithms, 18(3), 2022. URL: https://doi.org/10.1145/3519028.
  73. Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. k-apices of minor-closed graph classes. I. Bounding the obstructions. Journal of Combinatorial Theory, Series B, 161:180-227, 2023. URL: https://doi.org/10.1016/j.jctb.2023.02.012.
  74. Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M. Thilikos, and Alexandre Vigny. Model checking disjoint-paths logic on topological-minor-free graph classes, 2023. URL: https://arxiv.org/abs/2302.07033.
  75. Nicole Schirrmacher, Sebastian Siebertz, and Alexandre Vigny. First-Order Logic with Connectivity Operators. In Proc. of the 30th EACSL Annual Conference on Computer Science Logic (CSL), volume 216 of LIPIcs, pages 34:1-34:17, 2022. URL: https://doi.org/10.4230/LIPIcs.CSL.2022.34.
  76. Detlef Seese. Linear time computable problems and first-order descriptions. Mathematical Structures in Computer Science, 6(6):505-526, 1996. URL: https://doi.org/10.1017/S0960129500070079.
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 About DROPS Imprint Privacy Contact