# Liar's Domination in Unit Disk Graphs

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

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

Data updated: 2025-10-25T22:20:05.971Z

Authors: Ramesh K. Jallu, Sangram K. Jena, Gautam K. Das

Published: 2020-05-28T11:27:40.000Z

## Abstract

In this article, we study a variant of the minimum dominating set problem known as the minimum liar's dominating set (MLDS) problem. We prove that the MLDS problem is NP-hard in unit disk graphs. Next, we show that the recent sub-quadratic time $\\frac{11}{2}$-factor approximation algorithm \\cite{bhore} for the MLDS problem is erroneous and propose a simple $O(n + m)$ time 7.31-factor approximation algorithm, where $n$ and $m$ are the number of vertices and edges in the input unit disk graph, respectively. Finally, we prove that the MLDS problem admits a polynomial-time approximation scheme.

## 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/2005.13913>)

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