×

A linear time algorithm for liar’s domination problem in proper interval graphs. (English) Zbl 1284.05308

Summary: Let \(G=(V,E)\) be a graph without isolated vertices and having at least 3 vertices. A set \(L\subseteq V(G)\) is a liar’s dominating set if (1) \(| N_G[v]\cap L|\geqslant 2\) for all \(v\in V(G)\), and (2) \(|(N_G[u]\cup N_G[v])\cap L|\geqslant 3\) for every pair \(u,v\in V(G)\) of distinct vertices in \(G\), where \(N_G[x]=\{y\in V\mid xy\in E\}\cup\{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.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Booth, K. S.; Johnson, J. H., Dominating sets in chordal graphs, SIAM J. Comput., 11, 191-199 (1982) · Zbl 0485.05055
[2] Chang, M. S., Efficient algorithms for the domination problems on interval and circular-arc graphs, SIAM J. Comput., 27, 6, 1671-1694 (1998) · Zbl 0911.05051
[3] Fulkerson, D. R.; Gross, O. A., Incidence matrices and interval graphs, Pacific J. Math., 15, 835-855 (1965) · Zbl 0132.21001
[4] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Co.: W.H. Freeman and Co. San Francisco · Zbl 0411.68039
[5] Gavril, F., A recognition algorithm for the intersection graphs of paths in trees, Discrete Math., 23, 3, 211-227 (1978) · Zbl 0398.05060
[6] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel Dekker Inc.: Marcel Dekker Inc. New York · Zbl 0890.05002
[7] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Domination in Graphs, Advanced Topics (1998), Marcel Dekker Inc.: Marcel Dekker Inc. New York · Zbl 0883.00011
[8] Jamison, R. E.; Laskar, R., Elimination orderings of chordal graphs, (Combinatorics and Applications. Combinatorics and Applications, Calcutta, 1982 (1984), ISI: ISI Calcutta), 192-200
[9] Keil, J. M., Total domination in interval graphs, Inform. Process. Lett., 22, 117-174 (1986) · Zbl 0595.05063
[10] Laskar, R.; Pfaff, J.; Hedetniemi, S. M.; Hedetniemi, S. T., On the algorithm complexity of total domination, SIAM J. Alg. Discrete Methods, 5, 420-425 (1984) · Zbl 0576.68056
[11] Panda, B. S.; Das, S. K., A linear time recognition algorithm for proper interval graphs, Inform. Process. Lett., 87, 3, 153-161 (2003) · Zbl 1161.68855
[12] Roden, M. L.; Slater, P. J., Liarʼs domination in graphs, Discrete Math., 309, 19, 5884-5890 (2009) · Zbl 1211.05123
[13] Slater, P. J., Liarʼs domination, Networks, 54, 2, 70-74 (2009) · Zbl 1204.90061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.