Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds

Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, Petru Valicov

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:

  1. Identifying Codes: A set of vertices where every vertex in the graph has a unique, non-empty neighborhood within the set.
  2. Locating-Dominating Sets: Similar to identifying codes, but only requires unique neighborhoods for vertices outside the solution set.
  3. Metric Dimension: Uses the exact distances from a vertex to the set of sensors to create a unique signature.
Examples of identifying codes, open locating-dominating sets, and locating-dominating sets on interval graphs.

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.

Geometric construction used to establish the quadratic relationship between the number of sensors and the number of vertices in interval graphs.

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

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 \emph{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.
BibTeX
@article{foucaud2017identification,
  author = {Florent Foucaud and George B. Mertzios and Reza Naserasr and Aline Parreau and Petru Valicov},
  title = {{Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds}},
  journal = {Theoretical Computer Science},
  year = {2017},
  doi = {10.1016/j.tcs.2017.01.006},
}
Figure