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
1993437988 2001663593 2080619861 1564010364
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. par>We prove some non-approximability results for restrictions of basic combinatorial optimization problems to instances of bounded “degreeror bounded “width.” Specifically: We prove that the Max 3SAT problem on instances where each variable occurs in at most B clauses, is hard to approximate to within a factor @math , unless @math . H stad [18] proved that the problem is approximable to within a factor @math in polynomial time, and that is hard to approximate to within a factor @math . Our result uses a new randomized reduction from general instances of Max 3SAT to bounded-occurrences instances. The randomized reduction applies to other Max SNP problems as well. We observe that the Set Cover problem on instances where each set has size at most B is hard to approximate to within a factor @math unless @math . The result follows from an appropriate setting of parameters in Feige's reduction [11]. This is essentially tight in light of the existence of @math -approximate algorithms [20, 23, 9] We present a new PCP construction, based on applying parallel repetition to the inner verifier,'' and we provide a tight analysis for it. Using the new construction, and some modifications to known reductions from PCP to Hitting Set, we prove that Hitting Set with sets of size B is hard to approximate to within a factor @math . The problem can be approximated to within a factor B [19], and it is the Vertex Cover problem for B =2. The relationship between hardness of approximation and set size seems to have not been explored before. We observe that the Independent Set problem on graphs having degree at most B is hard to approximate to within a factor @math , unless P = NP . This follows from a comination of results by Clementi and Trevisan [28] and Reingold, Vadhan and Wigderson [27]. It had been observed that the problem is hard to approximate to within a factor @math unless P = NP [1]. An algorithm achieving factor @math is also known [21, 2, 30, 16 . 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. Thorup and Zwick showed that for any integer k≥ 1, it is possible to preprocess any positively weighted undirected graph G=(V,E), with |E|=m and |V|=n, in O(kmn @math ) expected time and construct a data structure (a (2k–1)-approximate distance oracle) of size O(kn @math ) capable of returning in O(k) time an approximation @math of the distance δ(u,v) from u to v in G that satisfies @math , for any two vertices u,v∈ V. They also presented a much slower O(kmn) time deterministic algorithm for constructing approximate distance oracle with the slightly larger size of O(kn @math log n). We present here a deterministic O(kmn @math ) time algorithm for constructing oracles of size O(kn @math ). Our deterministic algorithm is slower than the randomized one by only a logarithmic factor. Using our derandomization technique we also obtain the first deterministic linear time algorithm for constructing optimal spanners of weighted graphs. We do that by derandomizing the O(km) expected time algorithm of Baswana and Sen (ICALP’03) for constructing (2k–1)-spanners of size O(kn @math ) of weighted undirected graphs without incurring any asymptotic loss in the running time or in the size of the spanners produced.