Complexity results for identifying codes in planar graphs

Complexity results for identifying codes in planar graphs

0.00 Avg rating0 Votes
Article ID: iaor20107458
Volume: 17
Issue: 6
Start Page Number: 691
End Page Number: 710
Publication Date: Nov 2010
Journal: International Transactions in Operational Research
Authors: , , ,
Abstract:

Let G be a simple, undirected, connected graph with vertex set V(G) and 𝒞⊆V(G) be a set of vertices whose elements are called codewords. For vV(G) and r⩾1, let us denote by Ir 𝒞(v) the set of codewords c∈𝒞 such that d(v,c)⩽r, where the distance d(v,c) is defined as the length of a shortest path between v and c. More generally, for AV(G), we define Ir𝒞(A)=∪v∈AIr𝒞(V), which is the set of codewords whose minimum distance to an element of A is at most r. If r and l are positive integers, 𝒞 is said to be an (r,⩽l)-identifying code if one has I r 𝒞(A)≠Ir 𝒞(A′) whenever A and A′ are distinct subsets of V(G) with at most l elements. We consider the problem of finding the minimum size of an (r,⩽l)-identifying code in a given graph. It is already known that this problem is NP-hard in the class of all graphs when l=1 and r⩾1. We show that it is also NP-hard in the class of planar graphs with maximum degree at most three for all (r,l) with r⩾1 and l∈{1,2}. This shows, in particular, that the problem of computing the minimum size of an (r,⩽2)-identifying code in a given graph is NP-hard.

Reviews

Required fields are marked *. Your email address will not be published.