betaFeedback

WorksComputer Science

Model Checking for Metric Extensions of Monadic Second-Order Logic

Abstract

Monadic second-order logic yields powerful algorithmic meta-theorems, but cannot express that a vertex set induces a shortest path. We study metric extensions of counting monadic second-order logic and identify structural parameters supporting efficient model checking, optimization, and counting. We show that shortest paths and equidistance guarded by geodesic cycles are definable in ordinary vertex-set MSO on graph classes of bounded cycle-basis length. This yields fixed-parameter tractable model checking for the corresponding extensions of CMSO2, parameterized by formula length and bag-connected treewidth, and of CMSO1, parameterized by formula length and geodesic cliquewidth: the sum of cliquewidth and cycle-basis length. The translations preserve free variables, yielding additive optimization and counting. Applications include Minimum Geodetic Set and Strong Metric Dimension for geodesic cliquewidth, and Minimum Isometric Path Partition for bag-connected treewidth. We also introduce restricted packing-covering templates that allow numerical distance thresholds to remain outside the parameter. For each fixed template, feasibility, additive vertex-weight optimization, and counting are fixed-parameter tractable in bag-connected treewidth. Applications include Distance-r Dominating Set, d-Scattered Set, and Minimum Eccentricity Shortest Path. Finally, we characterize bounded bag-connected treewidth and bounded geodesic cliquewidth through monadic dependence for the corresponding guarded logics. Unguarded distance comparisons have stricter structural boundaries: first-order model checking is AW[*]-complete already on uncolored caterpillars, and model checking a fixed existential monadic sentence is NP-complete on this class.

Introduction

Courcelle’s theorem: algorithms, logic, and structure. Courcelle’s theorem is a cornerstone of parameterized algorithmics. It states that every fixed graph property expressible in monadic second-order logic with vertex- and edge-set quantification can be decided in linear time on graphs of bounded treewidth [41]. This gives a common explanation for the tractability of a wide range of otherwise difficult problems, including 3-Colorability and Hamiltonian Cycle, and makes logical definability a standard tool for proving fixed-parameter tractability. Expressing a decision problem by a fixed formula in this language already establishes fixed-parameter tractability in treewidth, without requiring a separate dynamic program and correctness proof. The theorem therefore both unifies existing algorithmic results and provides a systematic way to obtain new ones, including variants formed by combining constraints in the same language.

More precisely, monadic second-order logic (MSO) comes in two standard forms for graphs: its vertex-set form MSO1\mathrm{MSO}_1 quantifies over vertices and vertex sets, while its incidence form MSO2\mathrm{MSO}_2 additionally quantifies over edges and edge sets. The corresponding counting extensions CMSO1\mathrm{CMSO}_1 and CMSO2\mathrm{CMSO}_2 also allow predicates of the form ∣X∣≡a(modm)|X| \equiv a \pmod{m}, where aa and mm are constants specified in the formula. Courcelle’s theorem applies to CMSO2\mathrm{CMSO}_2 and gives a model-checking algorithm with running time f(∣φ∣+tw⁡(G))∣V(G)∣f(|\varphi|+\operatorname{tw}(G))|V(G)|, for a computable function ff. Thus the dependence on both the specification of the problem and the structural complexity of the graph is confined to the parameter-dependent factor. Additive optimization and evaluation extensions further yield algorithms for finding optimum solutions and counting solutions to logically specified problems [3, 37]. The corresponding algorithmic meta-theorem for CMSO1\mathrm{CMSO}_1 and cliquewidth is due to Courcelle, Makowsky, and Rotics [CMR00].

These algorithmic results have a striking structural counterpart: treewidth and cliquewidth also admit exact characterizations through the expressive power of the corresponding logics. Informally, a graph class is monadically dependent for a logic if no fixed transduction in that logic can produce all finite graphs from the class, even after adding a fixed finite collection of unary predicates. Classes of bounded treewidth are precisely the monadically (C)MSO2_2-dependent classes, and classes of bounded cliquewidth are precisely the monadically CMSO1_1-dependent classes. The Grid Minor Theorem of Robertson and Seymour, together with an interpretation argument underlying Seeše’s theorem, implies that every graph class of unbounded treewidth admits a fixed MSO2_2-interpretation producing all finite graphs from monadic lifts of its incidence structures [95, 96]. For cliquewidth, the corresponding characterization follows from a theorem of Courcelle and Oum [36]. The same structural restrictions that support the algorithmic meta-theorems therefore also mark the boundary beyond which the logics can encode arbitrary graphs. We define these logical notions formally below and refer to Pilipczuk’s survey [91] for further background.

Our results extend both aspects of this connection to metric graph problems. We develop meta-theorems for extensions of MSO that can express shortest paths and other metric constraints. For the logics of our first meta-theorem, we also obtain matching monadic-dependence characterizations of bounded bag-connected treewidth and bounded geodesic cliquewidth. Figure 1 places these characterizations at the side of the well-established correspondences between logic and graph structure.

Logics and graph classes captured through monadic dependence

Figure 1. Logics and the graph classes they capture through monadic dependence. Horizontal arrows indicate the capturing correspondences, and downward arrows indicate inclusion.

Metric extensions. A shortcoming of (C)MSO is that, in general, it cannot express that a set of vertices induces a shortest path with a fixed formula. Indeed, a standard Ehrenfeucht–Fraïssé argument already shows this on cycles, where no fixed (C)MSO formula can determine whether a designated arc is no longer than the complementary arc. This motivates us to study extensions of monadic second-order logic and first-order logic that address this shortcoming. We consider the following atoms.

  • SP⁡(P,s,t)\operatorname{SP}(P,s,t) expresses that the vertex set PP induces a shortest path from ss to tt.

  • EqGC⁡(C,x,y,u,v)\operatorname{EqGC}(C,x,y,u,v) expresses that CC induces a geodesic cycle containing x,y,u,vx,y,u,v and that dG(x,y)=dG(u,v)d_G(x,y)=d_G(u,v). A geodesic cycle is a cycle in which the distance between any two vertices, measured along the cycle, equals their distance in the whole graph.

  • Dist⁡(u,v,d)\operatorname{Dist}(u,v,d) expresses that dG(u,v)≥dd_G(u,v)\ge d, where dd is a numerical threshold.

  • The two restricted forms Sep⁡d(X,Y)\operatorname{Sep}_d(X,Y) and Cover⁡r(U,Y)\operatorname{Cover}_r(U,Y) of Dist⁡(u,v,d)\operatorname{Dist}(u,v,d) assert, respectively, that every pair of distinct vertices x∈Xx\in X and y∈Yy\in Y has distance at least dd, and that every vertex of UU lies at distance at most rr from some vertex of YY.

  • For the nearest-label atoms, we assume that the graph carries unary input predicates L1,…,LqL_1,\ldots,L_q that form a partition of V(G)V(G). We write NearLab⁡i(v;S)\operatorname{NearLab}_i(v;S) if at least one vertex of SS closest to vv has label ii, that is,

NearLab⁡i(v;S)⟺∃u∈S∩Li: dG(v,u)=dG(v,S).\operatorname{NearLab}_i(v;S)\Longleftrightarrow\exists u\in S\cap L_i:\ d_G(v,u)=d_G(v,S).
  • EqDist⁡(x,y,u,v)\operatorname{EqDist}(x,y,u,v) expresses that dG(x,y)=dG(u,v)<∞d_G(x,y)=d_G(u,v)<\infty.

  • Close⁡(x,u,v)\operatorname{Close}(x,u,v) expresses that dG(x,u)<dG(x,v)d_G(x,u)<d_G(x,v).

For a logic L\mathcal{L} and a collection F\mathcal{F} of these predicates, we write L[F]\mathcal{L}[\mathcal{F}], for example L[SP⁡,EqGC⁡]\mathcal{L}[\operatorname{SP},\operatorname{EqGC}], for the corresponding extension of L\mathcal{L}.

Model checking provides a bridge from logical descriptions to algorithms. Given a graph GG and a sentence φ\varphi, the question is whether φ\varphi is true in GG, in symbols G⊨φG \models\varphi. For a formula φ(X1,…,Xt)\varphi(X_1,\ldots,X_t) with free monadic variables, and a vertex-weighted graph GG, the corresponding optimization problem asks for a satisfying assignment that minimizes or maximizes a given additive weight function. Evaluation and optimization forms of Courcelle’s theorem were proved by Arnborg, Lagergren, and Seese and by Courcelle and Mosbah [3, 37]. For CMSO1_1, they extend to bounded cliquewidth [CMR00, CMR01]. These methods also yield counting of satisfying assignments to the free monadic variables. Our aim in this paper is to extend these meta-theorems to our more general logics and derive new parameterized algorithms for problems expressible in the respective logics. Below, we give many examples of problems expressible in these extensions of (C)MSO that are W[1]-hard when parameterized by treewidth alone, so we look for additional parameters that allow us to obtain fixed-parameter algorithms.

Width parameters and our first new meta-theorem. The bag-connected treewidth of a graph GG, denoted by ctw⁡(G)\operatorname{ctw}(G) and introduced by Diestel and Müller [54], is the minimum width of a tree decomposition of GG in which every bag induces a connected subgraph1. Clearly, we have tw⁡(G)≤ctw⁡(G)\operatorname{tw}(G) \le\operatorname{ctw}(G), since we impose an additional requirement on the bags, but already cycles show that the two parameters can differ substantially: while tw⁡(Cn)=2\operatorname{tw}(C_n)=2, we have ctw⁡(Cn)=⌈n/2⌉\operatorname{ctw}(C_n)=\lceil n/2\rceil. Thus, even on graphs of very small treewidth, requiring the bags to be connected may force us to use much larger bags.

In fact, large treewidth and long geodesic cycles are the only obstructions to bounded bag-connected treewidth: Diestel and Müller [54] proved that a graph class has bounded bag-connected treewidth if and only if it has bounded treewidth and there is a bound on the lengths of its geodesic cycles. Using the refinement of Hamann and Weißauer [70], we can equivalently replace the latter condition by bounded cycle-basis length. The cycle-basis length cbl⁡(G)\operatorname{cbl}(G) of a graph GG is the minimum, over all bases of the binary cycle space of GG, of the length of the longest cycle in the basis, with cbl⁡(G)=0\operatorname{cbl}(G)=0 when GG is a forest. We obtain our most precise algorithmic statements for the combined parameter tw⁡(G)+cbl⁡(G)\operatorname{tw}(G)+\operatorname{cbl}(G), but, for brevity, we will mostly refer to bag-connected treewidth as the parameter in what follows.

For dense graphs we follow the same idea and combine cliquewidth with cycle-basis length, defining the geodesic cliquewidth of GG by

gcw⁡(G):=cw⁡(G)+cbl⁡(G).\operatorname{gcw}(G) := \operatorname{cw}(G) + \operatorname{cbl}(G).

It is easy to observe (as we do below) that a graph class has bounded geodesic cliquewidth if and only if it has bounded cliquewidth and no arbitrarily long geodesic cycles, which explains our choice of terminology.

The algorithmic usefulness of bag-connected decomposition was recently demonstrated by Chakraborty et al. [CDF⁺] who gave a double exponential FPT-algorithm for GEODETIC SET parameterized by bag-connected treewidth. Given a graph GG and an integer kk, the objective of GEODETIC SET is to decide if GG has a set SS of vertices of cardinality at most kk and any vertex of GG lies in some shortest path between some pair of vertices in SS. Even though Chakraborty et al. [CDF⁺] proved that computing bag-connected treewidth exactly is W[1]-hard when parameterized by the optimal width, there is an FPT approximation algorithm is available whose approximation ratio depends only on that width. The hardness result contrasts with the fixed-parameter tractability of computing ordinary treewidth, but the approximation result still allows us to construct a bag-connected decomposition whose width is bounded by a function of the optimum, which is sufficient for many parameterized algorithms.

A strong feature of our work is that the meta-theorems arrive at an early stage in the algorithmic study of bag-connected treewidth, when only a few dedicated algorithms for this parameter are available. The general logical framework thus precedes a broad repertoire of problem-specific algorithms and provides new fixed-parameter algorithms across several areas of metric graph theory. For several problems, this extends the strongest previously known tractability results in terms of width and diameter. This makes the meta-theorems a starting point for developing the algorithmic potential of bag-connected treewidth, with weighted optimization and exact counting available alongside the decision results.

Our first main result is an algorithmic meta-theorem for the two parameters bag-connected treewidth and geodesic cliquewidth. For additive optimization, we assign signed binary weights to the vertices for each free vertex-set variable, and we minimize or maximize the sum of the weights over the corresponding selected sets. When we also have free edge-set variables, we allow weights on the edges in the same way. We therefore state the running times in terms of the total binary input length NN, including the weights.

Theorem 1.1. For each of the following logics, we can perform model checking, decide whether a satisfying assignment to the free monadic variables exists, compute an assignment minimizing or maximizing an additive weight objective, and count the satisfying assignments or the optimum assignments. For a computable function ff, we obtain the following running times.

(i) For φ∈CMSO2[SP,EqGC]\varphi\in\mathrm{CMSO}_{2}[\mathrm{SP},\mathrm{EqGC}], we can solve these problems in time f(∣φ∣+ctw⁡(G))NO(1)f(|\varphi|+\operatorname{ctw}(G))N^{O(1)}. Thus these problems are fixed-parameter tractable parameterized by ∣φ∣+ctw⁡(G)|\varphi|+\operatorname{ctw}(G), or equivalently by ∣φ∣+tw⁡(G)+cbl⁡(G)|\varphi|+\operatorname{tw}(G)+\operatorname{cbl}(G).

(ii) For φ∈CMSO1[SP,EqGC]\varphi\in\mathrm{CMSO}_{1}[\mathrm{SP},\mathrm{EqGC}], we can solve these problems in time f(∣φ∣+gcw⁡(G))NO(1)f(|\varphi|+\operatorname{gcw}(G))N^{O(1)}. Thus these problems are fixed-parameter tractable parameterized by ∣φ∣+gcw⁡(G)=∣φ∣+cw⁡(G)+cbl⁡(G)|\varphi|+\operatorname{gcw}(G)=|\varphi|+\operatorname{cw}(G)+\operatorname{cbl}(G).

When we have no binary weights, we can state the same running-time bounds with n:=∣V(G)∣n := |V(G)| instead of NN. Note that this still covers cardinality optimization, where we use unit weights for the selected sets whose total size we wish to minimize or maximize. We recall the background on the optimization and counting variants of Courcelle’s Theorem in § 2.7.

Let us highlight three algorithmic applications of the above theorem in the context of the so-called “distance-based covering” problems [31] which is an umbrella term for many algorithmic problems involving the shortest-path metric. A set S⊆V(G)S \subseteq V(G) is geodetic if every vertex lies on a shortest path between two vertices of SS. Given a graph GG and an integer kk, recall that the objective of Geodetic Set is to find a geodetic set of GG with cardinality at most kk. We describe the geodetic sets by the following fixed MSO1[SP]\mathrm{MSO}_{1}[\mathrm{SP}] formula, and we obtain the minimum size by minimizing ∣S∣|S| over its satisfying assignments. We then compare this minimum with the input bound kk.

φgeo(S):=∀v∃s∃t∃P(s∈S∧t∈S∧SP(P,s,t)∧v∈P).\varphi_{\mathrm{geo}}(S) := \forall v \exists s \exists t \exists P\left(s \in S \land t \in S \land\mathrm{SP}(P,s,t) \land v \in P\right).

Geodetic Set is W[1]-hard for the combined parameter consisting of solution size, pathwidth, and feedback vertex set number [72]. Recently, Tale [Tal25] proved that Geodetic Set is NP-hard even at constant pathwidth and feedback vertex set number. See [72 Tal25, 25, 59, 11, 34, 30] for more results on Geodetic Set.

Theorem 1.1 extends the earlier FPT result for bag-connected treewidth to geodesic cliquewidth. We also obtain the corresponding results for weighted optimization and exact counting of solutions or optimum solutions, although we do not repeat these statements now for every application.

Corollary 1.2. Geodetic Set is FPT w.r.t. gcw.

Geodetic Set is a representative of the broader class of “vertex selection” problems involving shortest paths. In § 8, we present more algorithmic problems that have been studied in metric and algorithmic graph theory and for which our meta-theorem provides more general or even completely new results.

A second application of Theorem 1.1 is Isometric Path Partition, where we are given a graph GG and an integer kk and ask whether we can partition V(G)V(G) into exactly kk shortest paths. This problem has been studied in structural and algorithmic graph theory [CDF+26b]. Isometric Path Partition is W[1]-hard parameterized by treewidth, but FPT parameterized by treewidth plus diameter [CDF+26b]. See [CDF+26b, FFM+25, PSST26, CMO+26] for more results on this topic.

Isometric Path Partition can be expressed with a MSO2[SP]\mathrm{MSO}_2[\mathrm{SP}] formula as follows. For an edge set FF, let CompF(C)\mathrm{Comp}_F(C) be the ordinary CMSO2\mathrm{CMSO}_2 formula saying that CC is a nonempty connected component of the spanning subgraph (V(G),F)(V(G), F). Isolated vertices are included as one-vertex components. Define

IPP(F):=∀C(CompF(C)→∃s∃t SP(C,s,t)).\mathrm{IPP}(F) := \forall C\left(\mathrm{Comp}_F(C) \to\exists s\exists t\,\mathrm{SP}(C,s,t)\right).

If IPP(F)\mathrm{IPP}(F) holds, then every connected component of (V(G),F)(V(G), F) has a vertex set CC that induces a shortest path in GG, where we also allow singleton paths. Since CC is connected in (V(G),F)(V(G), F) and every shortest path is induced, we must include every edge of G[C]G[C] in FF. Consequently, (V(G),F)(V(G), F) is a disjoint union of shortest paths and has exactly ∣V(G)∣−∣F∣|V(G)|-|F| connected components. Conversely, from any isometric path partition we obtain a satisfying edge set FF by taking the union of its path edges.

We can therefore use the additive optimization part of Theorem 1.1 to maximize ∣F∣|F|, which gives us a partition into the minimum possible number of shortest paths. A partition into exactly kk paths exists if and only if this minimum is at most kk and k≤∣V(G)∣k \leq|V(G)|, since we can split shortest paths into shorter shortest paths until we obtain the desired number of parts. This yields the following corollary.

Corollary 1.3. Isometric Path Partition is FPT w.r.t. ctw.

As above, Isometric Path Partition is a representative of the broader class of “shortest path selection” problems and in § 8, we highlight more algorithmic problems that have been studied in algorithmic graph theory and apply Theorem 1.1 to obtain FPT-algorithms w.r.t. bag-connected treewidth.

A third application of Theorem 1.1 concerns hitting geodesic cycles. Given a graph GG and an integer kk, the objective of Geodesic Cycle Transversal is to decide if GG has a subset S⊆V(G)S \subseteq V(G) with ∣S∣≤k|S| \leq k such that all geodesic cycles of GG contain a vertex of SS. Since Geodesic Cycle Transversal admits a fixed formula in MSO1[EqGC]\mathrm{MSO}_1[\mathrm{EqGC}], we have the following corollary.

Corollary 1.4. Geodesic Cycle Transversal is FPT w.r.t. gcw.

Proof techniques. Our approach to the shortest-path predicate builds on the work of Boulinier, Petit, and Villain [19, 20]. A path P=v0v1⋯vrP = v_0v_1 \cdots v_r is shortest if and only if there is a map λ:V(G)→Z\lambda: V(G) \to\mathbb{Z} whose values differ by at most one across each edge and increase by one along PP. Of course, an unbounded integer-valued map cannot be quantified directly in ordinary MSO. Here is the trick: For an integer M≥3M \ge3, we call a labeling c:V(G)→ZMc: V(G) \to\mathbb{Z}_M admissible if adjacent vertices receive equal or cyclically consecutive labels. If M>cbl⁡(G)M > \operatorname{cbl}(G), then every such labeling can be lifted to an integer-valued potential with the same signed edge differences. We prove this lifting statement by adapting a result of Boulinier, Petit, and Villain [19, 20]. A fixed cyclic labeling can be represented by MM unary sets, and hence is MSO1_1 definable.

We show this idea in Figure 2, where we color the vertices of a grid by their distances from ss modulo 55. In (a), the labels increase by one modulo 55 along the shortest path, while the detour in (b) has two steps in which they decrease. If we change the labels along the detour so that every step increases by one, while keeping the other labels unchanged, we obtain the coloring in (c), where three edges no longer satisfy our admissibility condition. In (d), we show one of these edges on a geodesic 44-cycle, which makes the problem with this coloring easy to see.

A grid illustrating shortest paths, detours, forced labels, and a local inconsistency

Figure 2. In a grid, the square faces form a cycle basis, so cbl⁡(G)=4\operatorname{cbl}(G) = 4 and we may choose M=5M = 5. In (a) and (b), every graph edge has increment −1-1, 00, or 11 modulo 55, but only the shortest path increases at every step. In (c), we overwrite the detour vertices by their indices 0,1,…,80,1,\ldots,8 modulo 55, leaving the other colors unchanged. The three dashed edges now fail the edge condition, and (d) shows one of them on a geodesic square. This square rejects the displayed attempted extension.

Theorem 1.5. For every integer M≥3M \ge3, there exists an MSO1_1 formula CertSP⁡M(P,x,y)\operatorname{CertSP}_M(P,x,y) of length polynomial in MM that, on every graph GG with cbl⁡(G)<M\operatorname{cbl}(G) < M, is equivalent to SP⁡(P,x,y)\operatorname{SP}(P,x,y).

Similarly, for EqGC, we compare two arcs of a geodesic cycle by subtracting their signed edge contributions in a common cyclic direction. We show that these differences sum to zero around the cycle precisely when the arc lengths agree. Again, the existence of such an integer potential is equivalent to a finite cyclic labeling, which can be quantified by MSO1_1. We obtain the following analogous theorem.

Theorem 1.6. For every integer M≥3M \ge3, there exists an MSO1_1 formula CertEqGCM(C,x,y,u,v)_M(C,x,y,u,v) of length polynomial in MM that, on every graph GG with cbl⁡(G)<M\operatorname{cbl}(G) < M, is equivalent to EqGC(C,x,y,u,v)(C,x,y,u,v).

References

  1. [1]Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. European Journal of Combinatorics, 36:322–330, 2014. doi:10.1016/j.ejc.2013.06.048.DOI
  2. [2]Júlio Araújo, Mitre C Dourado, Fábio Protti, and Rudini M Sampaio. Introduction to graph convexity: An algorithmic approach. Springer Nature, 2025. doi:10.1007/978-3-031-84128-6.DOI
  3. [3]Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12(2):308–340, 1991. doi:10.1016/0196-6774(91)90006-K.DOI
  4. [4]Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, NJ, 1993.
  5. [6][AWW24] Shyan Akmal, Virginia Vassilevska Williams, and Nicole Wein. Detecting disjoint shortest paths in linear time and more. In 51st International Colloquium on Automata, Languages, and Programming, volume 297 of Leibniz International Proceedings in Informatics, pages 9:1–9:17. Schloss Dagstuhl – Leibniz Zentrum für Informatik, 2024. arXiv:2404.15916, doi:10.4230/LIPIcs.ICALP.2024.9.DOI
  6. [7][BC10] Achim Blumensath and Bruno Courcelle. On the monadic second-order transduction hierarchy. Logical Methods in Computer Science, 6(2):1–28, 2010. doi:10.2168/LMCS-6(2:2)2010.DOI
  7. [8][BCFL25] Davide Bilò, Giordano Colli, Luca Forlizzi, and Stefano Leucci. On the (In)approximability of the monitoring edge geodetic set problem. In Ho-Lin Chen, Wing-Kai Hon, and Meng-Tsung Tsai, editors, 36th International Symposium on Algorithms and Computation (ISAAC 2025), volume 359 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1–14:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ISAAC.2025.14.DOI
  8. [9][BDFDSL26] Davide Bilò, Alessia Di Fonso, Gabriele Di Stefano, and Stefano Leucci. On the approximability of graph visibility problems. Theoretical Computer Science, 1067:115766, 2026. doi:10.1016/j.tcs.2026.115766.DOI
  9. [10][BDM+24] Aritra Banik, Sayani Das, Anil Maheshwari, Bubai Manna, Subhas C. Nandy, Krishna Priya K. M., Bodhayan Roy, Sasanka Roy, and Abhishek Sahu. Minimum consistent subset in trees and interval graphs. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, volume 323 of Leibniz International Proceedings in Informatics, pages 7:1–7:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. arXiv:2404.15487, doi:10.4230/LIPIcs.FSTTCS.2024.7.
  10. [11][BDMI25] Benjamin Bergougnoux, Oscar Defrain, and Fionn Mc Inerney. Enumerating minimal solution sets for metric graph problems. Algorithmica, 87(5):712–735, 2025. doi:10.1007/s00453-025-01300-4.DOI
  11. [12][BDPR18] Stéphane Bessy, Mitre C. Dourado, Lucia D. Penso, and Dieter Rautenbach. The geodetic hull number is hard for chordal graphs. SIAM Journal on Discrete Mathematics, 32(1):543–547, 2018. doi:10.1137/17M1131726.DOI
  12. [13][BFG25] Matthias Bentert, Fedor V. Fomin, and Petr A. Golovach. Tight approximation and kernelization bounds for vertex-disjoint shortest paths. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), volume 327 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.STACS.2025.17.DOI
  13. [14][BK17] Kristóf Bérczi and Yusuke Kobayashi. The directed disjoint shortest paths problem. In 25th Annual European Symposium on Algorithms (ESA 2017), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1–13:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.ESA.2017.13.DOI
  14. [15]Glencora Borradaile and Hung Le. Optimal dynamic program for r-domination problems over tree decompositions. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), volume 63 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:23. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.IPEC.2016.8.
  15. [16]J. A. Bondy and U. S. R. Murty. Graph Theory, volume 244 of Graduate Texts in Mathematics. Springer, London, 2008. doi:10.1007/978-1-84628-970-5.DOI
  16. [17]Matthias Bentert, André Nichterlein, Malte Renken, and Philipp Zschoche. Using a geometric lens to find k disjoint shortest paths. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1–26:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. arXiv:2007.12502, doi:10.4230/LIPIcs.ICALP.2021.26.DOI
  17. [18]Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305–1317, 1996. doi:10.1137/S0097539793251219.DOI
  18. [19]Christian Boulinier, Franck Petit, and Vincent Villain. When graph theory helps self-stabilization. In Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC ’04, pages 150–159, New York, NY, USA, 2004. Association for Computing Machinery. doi:10.1145/1011767.1011790.DOI
  19. [20]Christian Boulinier, Franck Petit, and Vincent Villain. Synchronous vs. asynchronous unison. Algorithmica, 51(1):61–80, 2008. doi:10.1007/s00453-007-9066-x.DOI
  20. [21]John T. Baldwin and Saharon Shelah. Second-order quantifiers and the complexity of theories. Notre Dame Journal of Formal Logic, 26(3):229–303, 1985. doi:10.1305/ndjfl/1093870870.DOI
  21. [24]Dibyayan Chakraborty, Oscar Defrain, Florent Foucau​d, Mathieu Mari, Sebastian Ordyniak, and Pra​fullkumar Tale. Connected tree decomposition(s): Parameterized complexity and algorithmic applications. To appear.
  22. [25]Dibyayan Chakraborty, Sandip Das, Florent Fouc​aud, Harmender Gahlawat, and Dimitri Lajou. Algorithms and complexity for geodetic sets on interval and chordal graphs. Information and Computation, 311:105456, 2026. doi:10.1016/j.ic.2026.105456.DOI
  23. [27]Serafino Cicerone, Alessia Di Fonso, Gabriele Di Stefano, Alfredo Navarra, and Francesco Piselli. Mutual and total mutual visibility in hypercube-like graphs. Applied Mathematics and Computation, 491:129216, 2025. doi:10.1016/j.amc.2024.129216.DOI
  24. [29]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, Cambridge, 2012. doi:10.1017/CBO9780511977619.DOI
  25. [30]Dibyayan Chakraborty, Florent Foucaud, Harmender Gahlawat, Subir Kumar Ghosh, and Bodhayan Roy. Hardness and approximation for the Geodetic Set problem in some graph classes. In Algorithms and Discrete Applied Mathematics (CALDAM 2020), volume 12016 of Lecture Notes in Computer Science, pages 102–115. Springer, 2020. doi:10.1007/978-3-030-39219-2_9.DOI
  26. [31]Dibyayan Chakraborty, Florent Foucaud, and Anni Hakanen. Distance-based (and path-based) covering problems for graphs of given cyclomatic number. Discrete Mathematics, 348(11):114595, 2025. doi:10.1016/j.disc.2025.114595.DOI
  27. [32]David M. Chickering, Dan Geiger, and David Heckerman. On finding a cycle basis with a shortest maximal cycle. Information Processing Letters, 54(1):55–58, 1995. doi:10.1016/0020-0190(94)00231-M.DOI
  28. [33]Zhi-Zhong Chen, Michelangelo Grigni, and Christos H. Papadimitriou. Map graphs. Journal of the ACM, 49(2):127–138, 2002. doi:10.1145/506147.506148.DOI
  29. [34]Dibyayan Chakraborty, Harmender Gahlawat, and Bodhayan Roy. Algorithms and complexity for geodetic sets on partial grids. Theoretical Computer Science, 979:114217, 2023. doi:10.1016/j.tcs.2023.114217.DOI
  30. [35]Victor Chepoi. Separation axiom S₃ for geodesic convexity in graphs, 2024. arXiv:2405.07512, doi:10.48550/arXiv.2405.07512.DOI
  31. [36]Bruno Courcelle and Sang il Oum. Vertex-minors, monadic second-order logic, and a conjecture by Seese. Journal of Combinatorial Theory, Series B, 97(1):91–126, 2007. doi:10.1016/j.jctb.2006.04.003.DOI
  32. [37]Bruno Courcelle and Mohamed Mosbah. Monadic second-order evaluations on tree-decomposable graphs. Theoretical Computer Science, 109(1–2):49–82, 1993. doi:10.1016/0304-3975(93)90064-Z.DOI
  33. [41]Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Information and Computation, 85(1):12–75, 1990. doi:10.1016/0890-5401(90)90043-H.DOI
  34. [42]Bruno Courcelle. The monadic second-order logic of graphs III: Tree-decompositions, minors and complexity issues. RAIRO – Theoretical Informatics and Applications, 26(3):257–286, 1992.DOI
  35. [43]Serafino Cicerone and Gabriele Di Stefano. Characterizing and computing in linear time mutual-visibility parameters in distance-hereditary graphs. Discrete Applied Mathematics, 376:359–373, 2025. doi:10.1016/j.dam.2025.07.026.DOI
  36. [44]Serafino Cicerone, Gabriele Di Stefano, Lara Drožek, Jaka Hedžet, Sandi Klavžar, and Ismael González Yero. Variety of mutual-visibility problems in graphs. Theoretical Computer Science, 974:114096, 2023. doi:10.1016/j.tcs.2023.114096.DOI
  37. [45]Rajesh Chitnis, Samuel Thomas, and Anthony Wirth. Lower bounds for approximate (& exact) k-Disjoint-Shortest-Paths. Theoretical Computer Science, 1072:115842, 2026. doi:10.1016/j.tcs.2026.115842.DOI
  38. [46]George B. Dantzig. Discrete-variable extremum problems. Operations Research, 5(2):266–288, 1957. doi:10.1287/opre.5.2.266.DOI
  39. [47]Subhadeep R. Dev, Sanjana Dey, Florent Foucaud, Krishna Narayanan, and Lekshmi Ramasubramony Sulochana. Monitoring edge-geodetic sets in graphs. Discrete Applied Mathematics, 377:598–610, 2025. doi:10.1016/j.dam.2025.08.041.DOI
  40. [48]Rod G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science, 141(1-2):109–131, 1995. doi:10.1016/0304-3975(94)00097-3.DOI
  41. [49]Yon Dourisboure and Cyril Gavoille. Tree-decompositions with bags of small diameter. Discrete Mathematics, 307(16):2008–2029, 2007. doi:10.1016/j.disc.2005.12.060.DOI
  42. [51]Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, Heidelberg, fifth edition, 2017. doi:10.1007/978-3-662-53622-3.DOI
  43. [52]Marc Distel. An improved quasi-isometry between graphs of bounded cliquewidth and graphs of bounded treewidth. Journal of Graph Theory, 112(4):409–420, 2026. doi:10.1002/jgt.70037.DOI
  44. [54]Reinhard Diestel and Malte Müller. Connected tree-width. Combinatorica, 38(2):381–398, 2018. doi:10.1007/s00493-016-3516-5.DOI
  45. [56]Tali Eilam-Tzoreff. The disjoint shortest paths problem. Discrete Applied Mathematics, 85(2):113–138, 1998. doi:10.1016/S0166-218X(97)00121-2.
  46. [58]Jörg Flum and Martin Grohe. Model-checking problems as a basis for parameterized intractability. Logical Methods in Computer Science, 1(1:2):1–36, 2005. doi:10.2168/LMCS-1(1:2)2005.DOI
  47. [59]Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. In 51st International Colloquium on Automata, Languages, and Programming, volume 297 of Leibniz International Proceedings in Informatics, pages 66:1–66:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. arXiv:2307.08149, doi:10.4230/LIPIcs.ICALP.2024.66.DOI
  48. [60]Florent Foucaud, Shih-Shun Kao, Ralf Klasing, Mirka Miller, and Joe Ryan. Monitoring the edges of a graph using distances. Discrete Applied Mathematics, 319:424–438, 2022. doi:10.1016/j.dam.2021.07.002.DOI
  49. [61]Florent Foucaud, Clara Marcille, R. B. Sandeep, Sagnik Sen, and S. Taruni. Algorithms and complexity for monitoring edge-geodetic sets in graphs. Information and Computation, 312:105460, 2026. doi:10.1016/j.ic.2026.105460.DOI
  50. [62]Pierre Fraigniaud and Nicolas Nisse. Connected treewidth and connected graph searching. In LATIN 2006: Theoretical Informatics, volume 3887 of Lecture Notes in Computer Science, pages 479–490. Springer, 2006. doi:10.1007/11682462_45.DOI
  51. [63]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. arXiv:1311.3899, doi:10.1145/3051095.DOI
  52. [64]Marinus Gottschau, Marcus Kaiser, and Clara Waldmann. The undirected two disjoint shortest paths problem. Operations Research Letters, 47(1):70–75, 2019. doi:10.1016/j.orl.2018.11.011.DOI
  53. [65]Agelos Georgakopoulos and Philipp Sprüssel. Geodetic topological cycles in locally finite graphs. The Electronic Journal of Combinatorics, 16(1):R144, 2009. doi: 10.37236/233.DOI
  54. [66]Martin Grohe and Nicole Schweikardt. First-order query evaluation with cardinality conditions. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’18, pages 253–266. ACM, 2018. arXiv: 1707.05945, doi:10.1145/3196959.3196970.DOI
  55. [67]Robert Ganian, Manolis Vasilakis, and Simon Wietheger. Improved learning with structure: Fine-grained complexity of minimum consistent subset, 2026. arXiv: 2607.28240, doi:10.48550/arXiv.2607.28240.DOI
  56. [68]S. L. Hakimi. Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research, 12(3):450–459, 1964. doi:10.1287/opre.12.3.450.DOI
  57. [69]Joseph D. Horton. A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM Journal on Computing, 16(2):358–366, 1987. doi:10.1137/0216026.DOI
  58. [70]Matthias Hamann and Daniel Weißauer. Bounding connected tree-width. SIAM Journal on Discrete Mathematics, 30(3):1391–1400, 2016. doi:10.1137/15M1044618.DOI
  59. [71]Oded Kariv and S. L. Hakimi. An algorithmic approach to network location problems. II: The p-medians. SIAM Journal on Applied Mathematics, 37(3):539–560, 1979. doi:10.1137/0137041.DOI
  60. [72]Leon Kellerhals and Tomohiro Koana. Parameterized complexity of Geodetic Set. Journal of Graph Algorithms and Applications, 26(4):401–419, 2022. doi:10.7155/jgaa.00601.DOI
  61. [74]Tuukka Korhonen and Daniel Lokshtanov. An improved parameterized algorithm for treewidth. SIAM Journal on Computing, pages STOC23–155–STOC23–214, 2024. Special Section STOC 2023. doi:10.1137/23M1595059.DOI
  62. [75]Telikepalli Kavitha, Christian Liebchen, Kurt Mehlhorn, Dimitrios Michail, Romeo Rizzi, Torsten Ueckerdt, and Katharina A. Zweig. Cycle bases in graphs: Characterization, algorithms, complexity, and applications. Computer Science Review, 3(4):199–243, 2009. doi:10.1016/j.cosrev.2009.08.001.DOI
  63. [76]Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structural parameters, tight bounds, and approximation for (k,r)-Center. Discrete Applied Mathematics, 264:90–117, 2019. arXiv:1704.08868, doi:10.1016/j.dam.2018.11.002.DOI
  64. [77]Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structurally parameterized d-scattered set. Discrete Applied Mathematics, 308:168–186, 2022. doi:10.1016/j.dam.2020.03.052.
  65. [78]Mamadou Moustapha Kanté, Thiago Marcilon, and Rudini Sampaio. On the parameterized complexity of the geodesic hull number. Theoretical Computer Science, 791:10–27, 2019. doi:10.1016/j.tcs.2019.05.005.DOI
  66. [79]Yusuke Kobayashi and Ryo Sako. Two disjoint shortest paths problem with nonnegative edge length. Operations Research Letters, 47(1):66–69, 2019. doi:10.1016/j.orl.2018.11.012.DOI
  67. [80]Martin Kučera and Ondřej Suchý. Minimum eccentricity shortest path problem with respect to structural parameters. Algorithmica, 85(3):762–782, 2023. doi:10.1007/s00453-022-01006-x.
  68. [81]William Lochet. A polynomial time algorithm for the k-disjoint shortest paths problem. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 169–178. Society for Industrial and Applied Mathematics, 2021. doi:10.1137/1.9781611976465.12.DOI
  69. [82]Nikolas Mählmann, Patrice Ossona de Mendez, Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M. Thilikos, and Alexandre Vigny. A logic for minor-free graph classes: Model checking, dependence, and combinatorial reconfiguration, 2026. arXiv:2610.05263, doi:10.48550/arXiv.2610.05263.DOI
  70. [84]Bar Menashe and Meirav Zehavi. Min-sum disjoint paths on subclasses of chordal graphs. Theoretical Computer Science, 1064:115723, 2026. doi:10.1016/j.tcs.2025.115723.DOI
  71. [86]Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics. Springer, Berlin, Heidelberg, 2012. doi:10.1007/978-3-642-27875-4.DOI
  72. [87]Kevin O’Bryant. A complete annotated bibliography of work related to Sidon sequences. The Electronic Journal of Combinatorics, 2004. Dynamic Survey DS11. doi:10.37236/32.DOI
  73. [89]Sang-il Oum and Paul Seymour. Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B, 96(4):514–528, 2006. doi:10.1016/j.jctb.2005.10.006.DOI
  74. [90]Ignacio M. Pelayo. Geodesic Convexity in Graphs. SpringerBriefs in Mathematics. Springer, New York, NY, 2013. doi:10.1007/978-1-4614-8699-2.DOI
  75. [91]Michał Pilipczuk. Graph classes through the lens of logic, 2025. arXiv:2501.04166, doi:10.48550/arXiv.2501.04166.DOI
  76. [92]Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Toruńczyk, and Alexandre Vigny. Algorithms and data structures for first-order logic with connectivity under vertex failures. In 49th International Colloquium on Automata, Languages, and Programming, volume 229 of Leibniz International Proceedings in Informatics, pages 102:1–102:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. arXiv:2111.03725, doi:10.4230/LIPIcs.ICALP.2022.102.DOI
  77. [94]Michał Pilipczuk, Giannos Stamoulis, and Michał Włodarczyk. Planar Disjoint Shortest Paths is fixed-parameter tractable. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4572–4583. Society for Industrial and Applied Mathematics, 2026. doi:10.1137/1.9781611978971.165.DOI
  78. [95]Neil Robertson and Paul D. Seymour. Graph minors. V. excluding a planar graph. Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986. doi:10.1016/0095-8956(86)90030-4.DOI
  79. [96]Detlef Seese. The structure of the models of decidable monadic theories of graphs. Annals of Pure and Applied Logic, 53(2):169–195, 1991. doi:10.1016/0168-0072(91)90054-P.DOI
  80. [97]Florian Seiffarth, Tamás Horváth, and Stefan Wrobel. Maximal closed set and half-space separations in finite closure systems. Theoretical Computer Science, 973:114105, 2023. doi:10.1016/j.tcs.2023.114105.DOI
  81. [98]Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M. Thilikos, and Alexandre Vigny. Model checking disjoint-paths logic on topological-minor-free graph classes. In Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’24, pages 68:1–68:12. Association for Computing Machinery, 2024. doi:10.1145/3661814.3662089.DOI
  82. [99]Ignasi Sau, Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M Thilikos, and Alexandre Vigny. Model checking for low monodimensionality fragments of CMSO on topological-minor-free graph classes, 2026. arXiv:2605.00192, doi:10.48550/arXiv.2605.00192.DOI
  83. [100]Nicole Schirrmacher, Sebastian Siebertz, and Alexandre Vigny. First-order logic with connectivity operators. ACM Transactions on Computational Logic, 24(4):30:1–30:23, 2023. doi:10.1145/3595922.DOI
  84. [101]Gabriele Di Stefano. Mutual visibility in graphs. Applied Mathematics and Computation, 419:126850, 2022. doi:10.1016/j.amc.2021.126850.

Paper details

vlnc:W_zzhbeu35
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents