Parameterized Enumeration of Minimal Defensive Alliances
En palabras de los autores
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.
Apareció: jueves, 24 de septiembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: Full version to conference submission