Covering Graphs with Shortest Paths

29 concepts15 papers1 proposal

Imagine you are designing a transit network, a communication routing protocol, or a facility placement strategy. A natural goal is to ensure that every location (vertex) in your network (graph) is easily accessible or monitored. In graph theory, this is often framed as a coverage problem: what is the minimum number of paths, or the smallest set of anchor vertices, needed to cover the entire graph?

The absolute ideal scenario is a single path that visits every vertex exactly once—a Hamiltonian path. However, as Jan Kratochvíl et al. note, finding such a path is a notoriously difficult NP-complete problem. To make coverage problems more applicable to real-world networks where efficiency matters, researchers constrain the paths to be shortest paths (also called isometric paths), where the distance between any two vertices along the path matches their true shortest distance in the entire graph.

This constraint introduces a fascinating computational tension. On one hand, shortest paths are highly structured. On the other hand, they are globally interdependent; changing a single edge can alter shortest paths across the entire network. A major line of research maps out the exact boundaries of this complexity, identifying precisely when shortest-path coverage is intractable and when specific structural properties make it easy.

Two Ways to Cover with Shortest Paths

To understand why these problems are challenging, we must look at how shortest-path coverage is mathematically framed. Two primary formulations dominate the literature:

  1. Isometric Path Cover (IPC): The goal is to find the minimum number of isometric paths such that every vertex in the graph lies on at least one path. As highlighted by Maël Dumas et al., restricting covers to shortest paths is a natural way to seek tractability compared to general path covers.
  2. Geodetic Set: Instead of choosing paths directly, you select a subset of "anchor" vertices. The geodetic closure of this subset includes all vertices that lie on any shortest path between any pair of anchors. The goal is to find a minimum-sized vertex subset whose geodetic closure is the entire graph. Leon Kellerhals et al. note that this problem is fundamentally NP-hard on general graphs.

Both problems force an algorithm to reason about the global distance topology of the graph. Because a shortest path cannot bend or loop back arbitrarily, local greedy choices rarely lead to a globally optimal cover.

The Persistent Wall of Intractability

Because general graphs are computationally intractable, researchers often look at restricted graph families—like chordal graphs, interval graphs, or grids—hoping that simpler structures yield efficient algorithms. Surprisingly, shortest-path coverage often remains stubbornly hard even under severe structural constraints.

Consider chordal graphs, which are graphs that contain no induced cycles of length four or more. Despite this clean tree-like structure, Dibyayan Chakraborty et al. proved that the Isometric Path Cover problem remains NP-hard for chordal graphs.

When we restrict the structure even further to interval graphs (graphs representing overlapping intervals on a line), the problem still resists easy solutions. Dibyayan Chakraborty et al. demonstrated that the Minimum Geodetic Set problem is NP-hard for interval graphs, even when the graph's degree is tightly bounded. Similarly, Dibyayan Chakraborty et al. showed that partitioning a graph's vertices into disjoint isometric paths remains NP-hard for split graphs, which can be cleanly split into a simple clique and an independent set.

This persistent hardness reveals an important intuition: local simplicity does not equal global predictability. Even if a graph lacks complex cycles, the combinations of shortest paths running through it can still encode hard combinatorial problems, such as the Set Multi-Cover or Exact 3-Cover problems (as seen in related domination problems studied by Arijit Bishnu et al.).

Finding the Boundaries of Tractability

Where does the problem finally become easy? Tractability emerges when a graph's structure completely eliminates path ambiguity or enforces a strict hierarchical order.

Trees and Bounded Treewidth

In a tree, there is exactly one unique path between any two vertices. This means every path in a tree is automatically an isometric path, removing the complex global coordination required by general graphs. Leveraging this property, Florent Foucaud et al. designed a linear-time algorithm for the Path Cover problem on trees, as well as an XP-time algorithm for graphs of bounded treewidth. Earlier work by R. Srikant 0001 et al. similarly found linear-time solutions for related path cover variants on block graphs and bipartite permutation graphs.

The Geometry of Grids: Solid vs. Partial

Perhaps the clearest intuition for why shortest-path coverage is hard comes from comparing solid grids to partial grids.

A solid grid is a perfect, unbroken lattice. Because there are no holes, the shortest paths between any two points follow highly predictable, geometric trajectories. Dibyayan Chakraborty et al. exploited this geometric predictability to create a linear-time algorithm for finding the minimum geodetic set in solid grids.

Solid Grid (Predictable Paths)       Partial Grid (Unpredictable Obstacles)
    +---+---+---+                        +---+   +---+
    |   |   |   |                        |   |   |   |
    +---+---+---+                        +---+   +---+
    |   |   |   |                        |       |   |
    +---+---+---+                        +---+---+---+
(Paths flow freely)                  (Paths must detour around holes)

However, if you punch holes in the lattice to create a partial grid, the situation changes entirely. Shortest paths must now navigate around these missing vertices, creating complex detours. This reintroduces global coordination complexity. As a result, Dibyayan Chakraborty et al. proved that the Minimum Geodetic Set problem becomes NP-hard even on subcubic partial grids.

Broader Structural Connections

The mathematical difficulty of managing paths and cuts is a recurring theme across graph theory. The boundaries discovered in shortest-path coverage mirror those found in other partitioning problems. For instance, Denis Cornaz et al. showed that the vertex $k$-cut problem—finding the minimum number of vertices to disconnect a graph into $k$ parts—is NP-hard for any fixed $k \ge 3$. Similarly, Zhao An et al. demonstrated that even partitioning simple trees into balanced bins using edge cuts is NP-complete.

This underlying complexity even carries over into competitive scenarios. When shortest-path coverage is turned into a game—where two players alternate selecting vertices to build a geodetic set—the inherent hardness of the underlying graph structure dictates whether a winning strategy can be found. As Antoine Dailly et al. demonstrated, universal polynomial-time algorithms for these games are out of reach for general networks, but become achievable on highly constrained, tree-like structures like block graphs and cacti.

Ultimately, this body of research shows that covering a graph with shortest paths is a delicate balancing act between local constraints and global geometry. By mapping out exactly which graph properties cause intractability, these researchers provide the theoretical foundation needed to design efficient approximation and parameterized algorithms for complex modern networks.

Key Foundational Work

On Finding Minimal w-cutset (2004) — contributed 3 concept elements to this direction.
Optimal Path Cover Problem on Block Graphs and Bipartite Permutation Graphs (1993) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_geodetic_set_complexity_57042029,
  title = {geodetic set complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geodetic-set-complexity/rdr_5704202968174c539896bef93413accc},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_geodetic_set_complexity_57042029_v1,
  title = {geodetic set complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geodetic-set-complexity/rdr_5704202968174c539896bef93413accc/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake