Computational Intractability of Graph Resolvability and Identification

23 concepts11 papers1 proposal

In graph theory, a recurring strategy for overcoming NP-hardness is to restrict the problem domain to structured graph classes. We often expect that families with rigid geometric or topological regularities—such as perfect graphs, interval graphs, or highly symmetric networks—will yield polynomial-time algorithms. For example, finding the maximum stable set of a graph is notoriously NP-hard because "imperfect" structural anomalies like odd holes and antiholes distort the underlying optimization polytope, as explained by [Haus] et al. in A Primal Approach to the Stable Set Problem. When these structures are forbidden, the problem becomes tractable.

However, a significant body of research reveals that this intuition breaks down for problems centered on graph identification, resolvability, and higher-order partitions. For these problems, local structural cleanliness fails to prevent global combinatorial explosions.

The Combinatorial Geometry of Graph Resolvability

To understand why these problems resist simplification, consider the concept of metric dimension, which acts as a discrete GPS network. The goal is to select a minimal subset of "landmark" or "detector" vertices such that every vertex in the graph possesses a unique vector of shortest-path distances to this subset.

As surveyed by [Tillquist] et al. in Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications, finding this minimal resolving set is NP-complete for general graphs. The fundamental difficulty stems from a coordinate-selection dilemma: choosing a landmark to distinguish one pair of vertices may inadvertently cause another pair to collapse into the same distance coordinates. As [Frongillo] et al. observe in Metric Dimension, this forces a brute-force search space that scales exponentially with the number of vertices.

This hardness is remarkably robust. Even when we limit the range of our detectors—a variation known as the $k$-truncated metric dimension—the problem remains NP-hard for arbitrary graphs, as shown by [Frongillo] et al. in Truncated metric dimension for finite graphs. Furthermore, the difficulty is not merely an issue of finding an exact optimum; it extends deeply into approximation limits. In Centroidal bases in graphs, [Klasing] et al. prove that finding a minimum set of relative detectors (a centroidal basis) is impossible to approximate within a factor of $o(\ln n)$ unless $P=NP$.

Why Structural Regularity Fails to Tame Distances

Why does restricting the graph class fail to alleviate this hardness? Consider interval graphs and permutation graphs, which can be cleanly represented by overlapping intervals on a line or intersecting lines between two parallel planes. These classes possess a natural linear ordering that typically trivializes path-based problems via dynamic programming.

Yet, [Foucaud] et al. demonstrate in Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs. II. Algorithms and Complexity that finding optimal identifying sets—such as metric dimension and locating-dominating sets—remains NP-complete even on interval and permutation graphs of limited diameter.

The intuition behind this failure lies in the difference between local neighborhoods and global path interactions:

  • In an interval graph, two intervals might be locally adjacent and share almost identical neighborhoods, making them hard to distinguish.
  • To resolve them, a landmark must be placed far away. However, because shortest paths in interval graphs can traverse many overlapping paths simultaneously, the distant landmark's signal becomes blurred, creating identical distance profiles for distinct internal nodes.

Because distance-based identification relies on these global, non-local interactions, the local ordering guarantees of interval graphs cannot prevent the problem from encoding hard combinatorial instances.

When structural constraints fail to guarantee tractability, researchers must either pivot to highly specific symmetric families—such as the exact structural path analysis used by [Wang] et al. in Determining the edge metric dimension of the generalized Petersen graph P(n, 3)—or deploy heavy algebraic machinery. For instance, in Resolvability of Hamming Graphs, [Laird] et al. show that even in highly structured, symmetric Hamming spaces, finding resolving sets requires combining integer linear programming with algebraic geometry (Gröbner bases) to reduce the dimensionality of the search space.

Higher-Order Hardness: Hypergraphs and Colored Partitions

This persistence of computational hardness is not unique to distance metrics; it also manifests in vertex partitioning and coding problems within perfect graphs. Perfect graphs are celebrated because their chromatic number equals their clique number for every induced subgraph, rendering standard vertex coloring and clique detection solvable in polynomial time.

However, this tractability vanishes when we shift our focus from the vertices themselves to the intersections of their maximal cliques. In On the complexity of bicoloring clique hypergraphs of graphs, [Tuza] et al. prove that bicoloring the clique hypergraph of a graph (coloring vertices such that no maximal clique is monochromatic) remains NP-hard even when restricted to perfect graphs.

Graph Domain (Perfect, Interval, Bipartite)
  │
  ├─► Local Problems (Coloring, Stable Set) ──► Tractable (Polynomial Time)
  │
  └─► Global/Higher-Order Problems ───────────► Intractable (NP-Hard)
        ├─► Distance Identification (Metric Dimension)
        ├─► Hypergraph Intersections (Clique Bicoloring)
        └─► Multi-Layer Constraints (Edge-Colored Clustering)

The intuition here is that while the underlying graph is structurally well-behaved, the overlap structure of its maximal cliques can form an arbitrarily complex hypergraph topology. The definition of a perfect graph places no constraints on how these higher-order hyperedges intersect globally, allowing NP-hardness to bypass the graph's vertex-level simplicity.

A similar phenomenon occurs with the perfect code problem (a strict variant of the dominating set problem). Eschen demonstrates in Algorithms for unipolar and generalized split graphs that this problem remains NP-complete even when restricted to chordal unipolar graphs, which are highly constrained subclasses of perfect graphs. The rigid requirement of a perfect code—that every vertex is dominated by exactly one code vertex—creates a fragile, global exact-cover constraint that cannot exploit the chordal or unipolar structure.

Finally, even if we simplify the graph topology all the way down to a bipartite structure, introducing multi-layer constraints can instantly reintroduce intractability. In Clustering on k-Edge-Colored Graphs, [Angel] et al. study the problem of partitioning vertices into clusters to maximize the weight of edges whose colors match their endpoints' cluster assignments. The authors prove this problem is NP-hard even for bipartite graphs where each vertex sees at most two edge colors. The intuition is that matching edge colors across a partition forces coordinated decisions across paths; choosing a color for one vertex triggers a cascade of constraints through its neighbors, mapping directly to the hard clauses of a MAX-2-SAT problem.

Summary

The shared insight across these developments is that graph structure is not a universal antidote to computational complexity. When a problem requires global coordination (like metric dimension) or captures higher-order intersections (like clique hypergraphs), the local structural guarantees of perfect, interval, or bipartite graphs fail to prevent combinatorial explosions.

Key Foundational Work

Clustering on k-Edge-Colored Graphs (2013) — contributed 4 concept elements to this direction.
On the complexity of bicoloring clique hypergraphs of graphs (2002) — contributed 3 concept elements to this direction.
Algorithms for Unipolar and Generalized Split Graphs (2013) — 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_np_hardness_for_perfect_graphs_37ceb5ef,
  title = {NP-hardness for perfect graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/np-hardness-for-perfect-graphs/rdr_37ceb5efd65f4964a6dcf7be3a5bc8d0},
  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_np_hardness_for_perfect_graphs_37ceb5ef_v1,
  title = {NP-hardness for perfect graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/np-hardness-for-perfect-graphs/rdr_37ceb5efd65f4964a6dcf7be3a5bc8d0/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