In many wireless networks, there is no fixed physical backbone nor centralized network management. The nodes of such a network have to self-organize in order to maintain a virtual backbone used to route messages. Moreover, any node of the network can be a priori at the origin of a malicious attack. Thus, in one hand the backbone must be fault-tolerant and in other hand it can be useful to monitor all network communications to identify an attack as soon as possible. We are interested in the minimum problem, a generalization of the classical minimum Vertex Cover problem, which allows to obtain a connected backbone. Recently, DelbotLP13 proposed a new centralized algorithm with a constant approximation ratio of @math for this problem. In this paper, we propose a distributed and self-stabilizing version of their algorithm with the same approximation guarantee. To the best knowledge of the authors, it is the first distributed and fault-tolerant algorithm for this problem. The approach followed to solve the considered problem is based on the construction of a connected minimal clique partition. Therefore, we also design the first distributed self-stabilizing algorithm for this problem, which is of independent interest.
Abstract The non-computability of many distributed tasks in anonymous networks is well known. This paper presents a deterministic self-stabilizing algorithm to compute a ( 3 − 2 Δ + 1 ) -approximation of a minimum vertex cover in anonymous networks. The algorithm operates under the distributed unfair scheduler, stabilizes after O ( n + m ) moves respectively O ( Δ ) rounds, and requires O ( log n ) storage per node. Recovery from a single fault is reached within a constant time and the contamination number is O ( Δ ) . For trees the algorithm computes a 2 -approximation of a minimum vertex cover. This paper presents a deterministic self-stabilizing algorithm that approximates a minimum vertex cover in anonymous networks with ratio 2 using the distributed scheduler and the link-register model with composite atomicity. No algorithm with a better approximation ratio can exist. The algorithm stabilizes in O(min n, Δ2, Δ log3 n ) rounds and requires O(Δ) memory per node. A vertex cover of a graph is a subset of vertices such that each edge has at least one endpoint in the subset. Determining the minimum vertex cover is a well-known NP-complete problem in a sequential setting. Several techniques, e.g., depth-first search, a local ratio theorem, and semidefinite relaxation, have given good approximation algorithms. However, some of them cannot be applied to a distributed setting, in particular self-stabilizing algorithms. Thus only a 2-approximation solution based on a self-stabilizing maximal matching has been obviously known until now. In this paper we propose a new self-stabilizing vertex cover algorithm that achieves (2–1 Δ)-approximation ratio, where Δ is the maximum degree of a given network. We first introduce a sequential (2–1 Δ)-approximation algorithm that uses a maximal matching with the high-degree-first order of vertices. Then we present a self-stabilizing algorithm based on the same idea, and show that the output of the algorithm is the same as that of the sequential one.