Abstract
We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets of an interval or a permutation graph. In these problems, one asks to find a subset of vertices, normally called a solution set, using which all vertices of the graph are distinguished. The identification can be done by considering the neighborhood within the solution set, or by employing the distances to the solution vertices. Normally the goal is to minimize the size of the solution set then. Here we study the case of interval graphs, unit interval graphs, (bipartite) permutation graphs and cographs. For these classes of graphs we give tight lower bounds for the size of such solution sets depending on the order of the input graph. While such lower bounds for the general class of graphs are in logarithmic order, the improved bounds in these special classes are of the order of either quadratic root or linear in terms of number of vertices. Moreover, the results for cographs lead to linear-time algorithms to solve the considered problems on inputs that are cographs.
Introduction
In network theory, a fundamental challenge involves determining the minimum number of "landmark" or "sensor" nodes required to uniquely identify every other node in a network. This problem has significant implications for fault detection, environmental monitoring, and navigation. While general graphs allow for highly efficient identification—where the number of nodes $n$ can be exponential relative to the number of sensors $k$—this paper demonstrates that structural constraints in common networks like interval and permutation graphs significantly limit this efficiency.
Problem Formulation
The authors investigate several variations of the identification problem, each defining a different way a "solution set" (the sensors) can distinguish vertices:
- Identifying Codes: A set of vertices where every vertex in the graph has a unique, non-empty neighborhood within the set.
- Locating-Dominating Sets: Similar to identifying codes, but only requires unique neighborhoods for vertices outside the solution set.
- Metric Dimension: Uses the exact distances from a vertex to the set of sensors to create a unique signature.
In general graphs, $n$ can be as large as $2^k - 1$, meaning $k \approx \log(n)$. However, for graphs representing physical or temporal constraints (like intervals on a timeline), these logarithmic bounds often fail to hold.
Methodology
The research leverages the geometric representations of specific graph classes rather than relying solely on abstract adjacency matrices:
- Interval Graphs: Vertices correspond to intervals on a real line; edges represent overlaps.
- Permutation Graphs: Vertices correspond to segments between two parallel lines.
- Cographs: Graphs constructed recursively via union and join operations, represented by "cotrees."
By analyzing the combinatorial limits of how these geometric shapes can overlap, the authors establish bounds on how many unique signatures can be generated by a set of $k$ sensors.
Key Insights and Bounds
The central finding is that geometric constraints prevent the "exponential packing" possible in general graphs. In interval and permutation graphs, it is impossible to arrange elements to create $2^k$ unique overlap patterns without a massive increase in the total number of elements.
As shown in the construction above, the number of identifiable intervals is bounded quadratically. Specifically, for interval graphs, $n \le \frac{k(k+3)}{2}$. This implies that the number of sensors $k$ must be at least proportional to $\sqrt{n}$, a significant departure from the logarithmic requirement in general graphs. For even more restricted classes, the relationship becomes linear ($n = O(k)$).
| Graph Class | Identifying Code / Locating-Dominating Set | Metric Dimension |
|---|---|---|
| General Graphs | $n \le 2^k - 1$ | No functional bound (can be $n$) |
| Interval Graphs | $n \le \frac{k(k+3)}{2}$ (Quadratic) | $n = O(Dk^2)$ |
| Permutation Graphs | $n \le k^2 + k - 2$ (Quadratic) | $n = O(Dk^2)$ |
| Unit Interval / Cographs | $n = O(k)$ (Linear) | $n = O(Dk)$ |
Conclusion
Beyond theoretical bounds, the paper provides a linear-time algorithm for finding optimal identifying codes and open locating-dominating sets in cographs by exploiting their cotree structure. This work highlights how structural properties dictate the efficiency of identification schemes. While this paper focuses on bounds, future work addresses the computational complexity of finding these sets and potential generalizations using VC-dimension.
Summary updated