Random subgraphs make identification affordable

Florent Foucaud, Guillem Perarnau, Oriol Serra

Abstract

An identifying code of a graph is a dominating set which uniquely determines all the vertices by their neighborhood within the code. Whereas graphs with large minimum degree have small domination number, this is not the case for the identifying code number, which is not a monotone parameter with respect to graph inclusion. We show that every graph $G$ with $n$ vertices, maximum degree $\Delta=\omega(1)$ and minimum degree $\delta\geq c\log{\Delta}$ contains a large spanning subgraph admitting an identifying code of size $O\left(\frac{n\log{\Delta}}{\delta}\right)$. This result is essentially best possible and utilizes an interplay of probabilistic methods, including the Lovász Local Lemma.

Introduction

In the field of network topology and monitoring, the concept of an identifying code serves as a vital framework for localization. An identifying code is a subset of vertices—effectively a set of sensors—such that every vertex in the graph is covered by at least one sensor, and the specific set of sensors covering any given vertex is unique. This uniqueness allows for the precise identification of a vertex (e.g., the location of a fault or a signal) based solely on which sensors are triggered.

A long-standing paradox in this area is that "more information" (more edges) does not necessarily lead to "better identification." In many graph-theoretic problems, increasing edge density simplifies tasks like domination. However, the identifying code number ($\gamma^{ID}$) is non-monotone. Adding edges can introduce symmetry, creating "twins"—vertices that are adjacent to the exact same set of sensors—thereby requiring a larger code to distinguish them. In extreme cases, dense graphs may require nearly all vertices to be part of the code, making monitoring prohibitively expensive.

The Problem of Symmetry in Dense Graphs

The primary obstacle to efficient identification is the existence of vertices with identical neighborhoods. In a dense graph, the likelihood of two vertices sharing the same set of neighbors increases. To resolve these symmetries, one must add more sensors to the code.

Foucaud, Perarnau, and Serra (2018) address this by asking: Can we strategically remove edges to break these symmetries? If we can find a spanning subgraph $G'$ of $G$ that has a small identifying code, we can effectively monitor the original network $G$ by only considering the connections present in $G'$.

Methodology: The Probabilistic Approach

The authors utilize the Probabilistic Method to prove the existence of such subgraphs. Rather than providing a deterministic algorithm, they demonstrate that a random subgraph construction succeeds with non-zero probability. The proof involves three main stages:

  1. Random Code Selection: A candidate code $C$ is formed by selecting each vertex independently with a probability $p$, calculated based on the graph's degree properties.
  2. Random Edge Deletion: To break symmetries, the authors define a random spanning subgraph model. Edges incident to the candidate code $C$ are deleted with a specific probability. This process is designed to ensure that no two vertices end up with the same "signature" (the set of sensors in $C$ that cover them).
  3. Probabilistic Analysis: To ensure the construction works globally, the authors employ the Chernoff Inequality to bound the size of the code and the Lovász Local Lemma (LLL). The LLL is particularly crucial here; it allows the authors to show that a collection of "bad events" (such as two vertices remaining twins) can be avoided simultaneously, provided that the dependencies between these events are sufficiently localized.

Key Results and Insights

The central contribution of the paper is the following theorem: Theorem: For any graph $G$ with $n$ vertices, if the minimum degree $\delta$ satisfies $\delta \geq 66 \log \Delta$, there exists a spanning subgraph $G'$ such that the identifying code size $\gamma^{ID}(G')$ is $O\left(\frac{n \log \Delta}{\delta}\right)$.

Asymptotic Optimality

The bound $O\left(\frac{n \log \Delta}{\delta}\right)$ is significant because it matches the order of the best possible domination number for graphs with these degree constraints. In particular, if a graph is very dense ($\delta = \Theta(n)$), the theorem implies the existence of a subgraph with an identifying code of size $O(\log n)$, which is asymptotically optimal.

Efficiency of the Subgraph

The number of edges removed to achieve this identification is relatively small, approximately $O(n \log \Delta)$. This suggests that the fundamental structure or "skeleton" of the original graph is preserved, even as the identifying code becomes much more "affordable."

Extension to Watching Systems

The paper also extends these findings to watching systems, a generalization where sensors can have different zones of coverage. The authors provide a new upper bound for the watching number $w(G)$, improving upon previous results for dense graphs and further demonstrating the power of the probabilistic deletion method.

Limitations and Future Directions

While the paper provides a robust theoretical foundation, several questions remain:

  • Algorithmic Implementation: The use of the Lovász Local Lemma makes the proof existential. While algorithmic versions of the LLL exist, applying them to this specific edge-deletion model to find the subgraph in polynomial time remains a non-trivial challenge.
  • The Degree Constraint: The current theorem requires $\delta \geq c \log \Delta$. The authors pose "Question 17," inquiring whether the $\log \Delta$ term can be replaced by $\log \delta$, which would broaden the applicability of the result.
  • Constant Optimization: The constants used in the proof (e.g., 66, 83, and 134) are chosen to ensure the mathematical arguments hold and are likely larger than what is required in practical applications.

Conclusion

By demonstrating that random subgraphs can significantly reduce the cost of identification, Foucaud, Perarnau, and Serra provide a powerful counter-argument to the intuition that more edges are always better. Their work bridges the gap between domination and identification, showing that with a small amount of "strategic forgetting," even the most complex and symmetric networks can be made navigable.

Summary updated

Abstract

An identifying code of a graph is a dominating set which uniquely determines all the vertices by their neighborhood within the code. Whereas graphs with large minimum degree have small domination number, this is not the case for the identifying code number (the size of a smallest identifying code), which indeed is not even a monotone parameter with respect to graph inclusion. We show that every graph $G$ with $n$ vertices, maximum degree $\Delta=\omega(1)$ and minimum degree $\delta\geq c\log{\Delta}$, for some constant $c>0$, contains a large spanning subgraph which admits an identifying code with size $O\left(\frac{n\log{\Delta}}{\delta}\right)$. In particular, if $\delta=\Theta(n)$, then $G$ has a dense spanning subgraph with identifying code $O\left(\log n\right)$, namely, of asymptotically optimal size. The subgraph we build is created using a probabilistic approach, and we use an interplay of various random methods to analyze it. Moreover we show that the result is essentially best possible, both in terms of the number of deleted edges and the size of the identifying code.
BibTeX
@article{foucaud2016random,
  author = {Florent Foucaud and Guillem Perarnau and Oriol Serra},
  title = {{Random subgraphs make identification affordable}},
  journal = {Journal of Combinatorics},
  year = {2016},
  doi = {10.4310/joc.2017.v8.n1.a3},
}
Figure