Algorithms reveal limits for finding minimal defensive alliances in networks
Parameterized Enumeration of Minimal Defensive Alliances
Logic in Computer Science
Summary
This paper studies how hard it is to list all the smallest groups in a network that can defend themselves against outsiders. The authors show a new fast method to find these groups in some types of networks with limited connections. They also prove it’s impossible to do this efficiently in some other types of networks unless a famous math problem is solved. Additionally, they find that by using certain ways to measure network structure, some fast methods are possible while others are not. This helps us understand when finding these defensive groups is manageable or infeasible.
What this means in practice
- •For network security engineers: Identify small self-defending clusters in communication networks with limited maximum connections using polynomial-delay enumeration algorithms.
- •For graph algorithm developers: Avoid attempting efficient enumeration of minimal defensive alliances in certain network types where it is theoretically proven to be impossible.
A theory result. No direct application yet.
Authors
Henning Fernau, Kevin Mann, Arne Meier, Heribert Vollmer
Abstract
In this paper, we consider the complexity of enumerating inclusion minimal defensive alliances. We present a polynomial-delay algorithm on graphs with maximum degree 5. We complement this result by proving that there is no output-polynomial algorithm on bipartite graphs with maximum degree 6 and degeneracy 2, unless P = NP. Furthermore, there is an FPT-delay algorithm when parameterized by neighborhood diversity. This result is the first exploit of a recently published enumeration algorithm for ILPs. By way of contrast, we prove that, for the parameter pathwidth, there is no FPT-delay algorithm for enumerating all inclusion minimal defensive alliances (unless FPT = W[1]). To the best of our knowledge, this is the first non-enumerability result using parameterized complexity for variations of Another/Next-problems.