Complexity and Approximation for Discriminating and Identifying Code Problems in Geometric Setups

Abstract

We study geometric variations of the discriminating code problem. In the \emph{discrete version} of the problem, a finite set of points $P$ and a finite set of objects $S$ are given in ${\mathbb{R}}^d$. The objective is to choose a subset $S^{\ast }\subseteq S$ of minimum cardinality such that for each point $p_i\in P$, the subset $S_i^{\ast }\subseteq S^{\ast }$ covering $p_i$ satisfies $S_i^{\ast }\ne \varnothing$, and each pair $p_i,p_j\in P$, $i\ne j$, we have $S_i^{\ast }\ne S_j^{\ast }$. In the \emph{continuous version} of the problem, the solution set $S^{\ast }$ can be chosen freely among a (potentially infinite) class of allowed geometric objects. In the 1-dimensional case ($d=1$), the points in $P$ are placed on a horizontal line $L$, and the objects in $S$ are finite-length line segments aligned with $L$ (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial-time solvable. Still, for the 1-dimensional discrete version, we design a polynomial-time $2$-approximation algorithm. We also design a PTAS for both discrete and continuous versions in one dimension, for the restriction where the intervals are all required to have the same length. We then study the 2-dimensional case ($d=2$) for axis-parallel unit square objects. We show that both continuous and discrete versions are NP-complete, and design polynomial-time approximation algorithms that produce $(16\cdot OPT+1)$-approximate and $(64\cdot OPT+1)$-approximate solutions respectively, using rounding of suitably defined integer linear programming problems. We show that the identifying code problem for axis-parallel unit square intersection graphs (in $d=2$) can be solved in the same manner as for the discrete version of the discriminating code problem for unit square objects.

References in corpus (4)

• Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity
• Identifying codes in hereditary classes of graphs and VC-dimension
• Partitioning Perfect Graphs into Stars
• Parameterized and Approximation Complexity of Partial VC Dimension