Abstract

Let  be a graph and  Then a vertex c of G is called a codeword if  otherwise c is called a non-codeword. The set S is called a Multiple Intruder Locating Dominating (MILD) set if every non-codeword v is adjacent to a codeword c which is not adjacent to any other non-codeword other than v. The cardinal of a minimum MILD set of graph G is called its MILD number, denoted by  The problem of finding the MILD number of a graph is known to be NP-complete for arbitrary graphs. In this paper, we present a simple approximation algorithm to find the MILD number of an arbitrary graph. We then consider the question of whether a polynomial time approximation scheme can be devised for the problem in bipartite and chordal graphs. Finally, the parameterized complexity of the MILD problem is discussed.

multiple intruder locating domination, APX-completeness, fixed parameter tractable.

Received: September 20, 2023; Accepted: December 21, 2023; Published: January 12, 2024

How to cite this article: K. A. Vidya and K. Venugopal, On approximation of multiple intruder locating domination number of a graph, Advances and Applications in Discrete Mathematics 41(1) (2024), 77-96. http://dx.doi.org/10.17654/0974165824005

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:
[1] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela and M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties, U.S. Government Printing Office, 1999.
[2] Maw-Shang Chang, Efficient algorithms for the domination problems on interval and circular-arc graphs, SIAM J. Comput. 27(6) (1998), 1671-1694.
[3] E. Cockayne, S. Goodman and S. Hedetniemi, A linear algorithm for the domination number of a tree, Inform. Process. Lett. 4(2) (1975), 41-44.
[4] E. J. Cockayne and S. T. Hedetniemi, Towards a theory of domination in graphs, Networks 7(3) (1977), 247-261.
[5] M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh, Parameterized Algorithms, Volume 4, Springer, 2015.
[6] R. G. Downey and M. R. Fellows, Fixed-parameter tractability and completeness, Congr. Numer. 87 (1992), 161-178.
[7] R. G. Downey and M. R. Fellows, Fundamentals of parameterized complexity, Texts in Computer Science, Springer, London, 2013.
[8] P. Flach and L. Volkmann, Estimations for the domination number of a graph, Discrete Math. 80(2) (1990), 145-151.
[9] J. Flum and M. Grohe, Parameterized complexity theory (Texts in Theoretical Computer Science, An EATCS Series), Springer-Verlag, Berlin, Heidelberg, 2006.
[10] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Domination in graphs: advanced topics, Monographs and Textbooks in Pure and Applied Mathematics 209, 1998.
[11] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, CRC Press, 1998.
[12] C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, J. Comput. System Sci. 43(3) (1991), 425 440.
[13] L. A. Sanchis, Maximum number of edges in connected graphs with a given domination number, Discrete Math. 87(1) (1991), 65-72.
[14] K. Venugopal and K. A. Vidya, Multiple intruder locating dominating sets, International Journal of Scientific Research in Mathematical and Statistical Sciences 6(2) (2019), 394-398.
[15] K. Venugopal and K. A. Vidya, Multiple intruder locating dominating sets in graphs: an algorithmic approach, Communications in Mathematics and Applications 11(2) (2020), 259-269.
[16] K. Venugopal and K. A. Vidya, Multiple intruder locating domination in infinite grids, Advances and Applications in Discrete Mathematics 24(1) (2020), 1-12.
[17] K. Venugopal and K. A. Vidya, Multiple intruder locating domination in chordal and bipartite graphs, Advances and Applications in Mathematical Sciences 21(10) (2022), 5731-5742.