# Hardness of Liar's Domination on Unit Disk Graphs

Source: [Hardness of Liar's Domination on Unit Disk Graphs](<https://www.sota2.com/research/paper/68fa63011e209131ce9fc3d3>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T20:31:19.733Z

Authors: Ramesh K Jallu, Gautam K Das

Published: 2016-11-23T14:21:02.000Z

## Abstract

A unit disk graph is the intersection graph of a set of unit diameter disks in the plane. In this paper we consider liar's domination problem on unit disk graphs, a variant of dominating set problem. We call this problem as {\\it Euclidean liar's domination problem}. In the Euclidean liar's domination problem, a set ${\\cal P}=\\{p\_1,p\_2,\\ldots,p\_n\\}$ of $n$ points (disk centers) are given in the Euclidean plane. For $p \\in {\\cal P}$, $N\[p\]$ is a subset of ${\\cal P}$ such that for any $q \\in N\[p\]$, the Euclidean distance between $p$ and $q$ is less than or equal to 1, i.e., the corresponding unit diameter disks intersect. The objective of the Euclidean liar's domination problem is to find a subset $D\\; (\\subseteq {\\cal P})$ of minimum size having the following properties : (i) $\|N\[p\_i\] \\cap D\| \\geq 2$ for $1 \\leq i \\leq n$, and (ii) $\|(N\[p\_i\] \\cup N\[p\_j\]) \\cap D\| \\geq 3$ for $i\\neq j, 1\\leq i,j \\leq n$. This article aims to prove the Euclidean liar's domination problem is NP-complete.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1611.07808>)

[PDF](<https://arxiv.org/pdf/1611.07808.pdf>)