Efficient model checking for graphs with metric logic extensions
Model Checking for Metric Extensions of Monadic Second-Order Logic
Logic in Computer Science
Summary
Graphs are networks made of points connected by lines, and sometimes it’s important to find special paths or distances in them. However, usual logical tools can’t easily express things like shortest paths. This paper studies extended logical frameworks that add distance and counting capabilities, and identifies ways to efficiently check logical statements about graphs with certain structures. The authors also connect these new methods to how complex or simple the graph is, helping decide when such checks are computationally manageable.
What this means in practice
- •For network algorithm designers: Enable efficient checking and optimization of shortest path-related properties on networks with bounded geodesic cliquewidth.
- •For graph database engineers: Support reasoning and counting queries involving distances and paths in graphs with bounded bag-connected treewidth.
Authors
Dibyayan Chakraborty, Sebastian Ordyniak, Sebastian Siebertz
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.