TY - GEN
T1 - Approximation Algorithm and Hardness Results for Defensive Domination in Graphs
AU - Henning, Michael A.
AU - Pandey, Arti
AU - Tripathi, Vikash
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - In a graph G= (V, E), a non-empty set A of k distinct vertices, is called a k-attack on G. The vertices in the set A is considered to be under attack. A set D⊆ V can defend or counter the attack A on G if there exists a one to one function f: A⟼ D, such that either f(u) = u or there is an edge between u and it’s image f(u), in G. A set D is called a k-defensive dominating set, if it defends against any k-attack on G. Given a graph G= (V, E), the minimum k-defensive domination problem requires us to compute a minimum cardinality k-defensive dominating set of G. When k is not fixed, it is co-NP-hard to decide if D⊆ V is a k-defensive dominating set. However, when k is fixed, the decision version of the problem is NP-complete for general graphs. On the positive side, the problem can be solved in linear time when restricted to paths, cycles, co-chain graphs and threshold graphs for any k. In this paper, we mainly focus on the problem when k> 0 is fixed. We prove that the decision version of the problem remains NP-complete for bipartite graphs, this answers a question asked by Ekim et al. (Discrete Math. 343 (2) (2020)). We give lower and upper bound on the approximation ratio for the problem. Further, we show that the minimum k-defensive domination problem is APX-complete for bounded degree graphs. On the positive side, we show that the problem is efficiently solvable for complete bipartite graphs for any k> 0.
AB - In a graph G= (V, E), a non-empty set A of k distinct vertices, is called a k-attack on G. The vertices in the set A is considered to be under attack. A set D⊆ V can defend or counter the attack A on G if there exists a one to one function f: A⟼ D, such that either f(u) = u or there is an edge between u and it’s image f(u), in G. A set D is called a k-defensive dominating set, if it defends against any k-attack on G. Given a graph G= (V, E), the minimum k-defensive domination problem requires us to compute a minimum cardinality k-defensive dominating set of G. When k is not fixed, it is co-NP-hard to decide if D⊆ V is a k-defensive dominating set. However, when k is fixed, the decision version of the problem is NP-complete for general graphs. On the positive side, the problem can be solved in linear time when restricted to paths, cycles, co-chain graphs and threshold graphs for any k. In this paper, we mainly focus on the problem when k> 0 is fixed. We prove that the decision version of the problem remains NP-complete for bipartite graphs, this answers a question asked by Ekim et al. (Discrete Math. 343 (2) (2020)). We give lower and upper bound on the approximation ratio for the problem. Further, we show that the minimum k-defensive domination problem is APX-complete for bounded degree graphs. On the positive side, we show that the problem is efficiently solvable for complete bipartite graphs for any k> 0.
KW - APX-completeness
KW - Approximation algorithms
KW - Defensive domination
KW - Domination
KW - Graph algorithms
KW - NP-completeness
UR - http://www.scopus.com/inward/record.url?scp=85121781933&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-92681-6_21
DO - 10.1007/978-3-030-92681-6_21
M3 - Conference contribution
AN - SCOPUS:85121781933
SN - 9783030926809
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 247
EP - 261
BT - Combinatorial Optimization and Applications - 15th International Conference, COCOA 2021, Proceedings
A2 - Du, Ding-Zhu
A2 - Du, Donglei
A2 - Wu, Chenchen
A2 - Xu, Dachuan
PB - Springer Science and Business Media Deutschland GmbH
T2 - 15th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2021
Y2 - 17 December 2021 through 19 December 2021
ER -