In this article, we study generalized liar's dominating set problem in graphs. Let @math be a simple undirected graph. The generalized liar's dominating set, called as the distance- @math @math -liar's dominating set, is a subset @math such that (i) each vertex in @math is distance- @math dominated by at least @math vertices in @math , and (ii) each pair of distinct vertices in @math is distance- @math dominated by at least @math vertices in @math , where @math are positive integers and @math . Here, a vertex @math is distance- @math dominated by another vertex @math means the shortest path distance between @math and @math is at most @math in @math . We first consider distance-1 @math -liar's dominating set problem and prove that it is NP-complete. Next, we consider distance- @math @math -liar's dominating set problem and show that it is also NP-complete. These liar's dominating set problems are generalized version of liar's dominating set problem as researcher studied only distance- @math @math -liar's dominating set problem in literature. We also prove that (i) distance-1 @math -liar's dominating set problem cannot be approximated within a factor of @math for any @math , unless NP @math DTIME @math , and (ii) distance- @math @math -liar's dominating set problem cannot be approximated within a factor of @math for any @math , unless NP @math DTIME @math .
@cite_0 studied the approximability of the problem in general graphs and given an @math -factor approximation algorithm, where @math is the maximum degree of the given graph. For proper interval graphs also Panda and Paul @cite_9 considered the problem and proposed a linear time algorithm. They also studied the minimum distance- @math @math -LDS problem for bounded degree graphs, and @math -claw free graphs @cite_0 . Sterling @cite_8 presented bounds on liar's domination number by considering the problem on two-dimensional grid graphs.
@cite_0 @cite_9 @cite_8
2080619861 1993437988 120391622
A subset L ? V of a graph G = ( V , E ) is called a liar's dominating set of G if (i) | N G u ] ? L | ? 2 for every vertex u ? V , and (ii) | ( N G u ] ? N G v ] ) ? L | ? 3 for every pair of distinct vertices u , v ? V . The Min Liar Dom Set problem is to find a liar's dominating set of minimum cardinality of a given graph G and the Decide Liar Dom Set problem is the decision version of the Min Liar Dom Set problem. The Decide Liar Dom Set problem is known to be NP-complete for general graphs. In this paper, we first present approximation algorithms and hardness of approximation results of the Min Liar Dom Set problem in general graphs, bounded degree graphs, and p-claw free graphs. We then show that the Decide Liar Dom Set problem is NP-complete for doubly chordal graphs and propose a linear time algorithm for computing a minimum liar's dominating set in block graphs. Let G=(V,E) be a graph without isolated vertices and having at least 3 vertices. A set L@?V(G) is a liar@?s dominating set if (1) |N"G[v]@?L|>=2 for all v@?V(G), and (2) |(N"G[u]@?N"G[v])@?L|>=3 for every pair u,v@?V(G) of distinct vertices in G, where N"G[x]= y@?V|xy@?E @? x is the closed neighborhood of x in G. Given a graph G and a positive integer k, the liar@?s domination problem is to check whether G has a liar@?s dominating set of size at most k. The liar@?s domination problem is known to be NP-complete for general graphs. In this paper, we propose a linear time algorithm for computing a minimum cardinality liar@?s dominating set in a proper interval graph. We also strengthen the NP-completeness result of liar@?s domination problem for general graphs by proving that the problem remains NP-complete even for undirected path graphs which is a super class of proper interval graphs.