Parameterized Enumeration of Minimal Defensive Alliances

• Inclusion minimality requires that no proper subset of an alliance is an alliance, unlike local minimality, which checks only single-vertex deletions.The paper notes that the property is non-monotone and that inclusion minimal defensive alliances are connected.Source: §1 · pp. 1–2
• Feng et al. provide the only published enumeration results identified by the authors, including an optimal O*(2^n)-time algorithm.Their results include both input-sensitive and output-sensitive enumeration.Source: §1 · p. 2
• The paper establishes polynomial-delay enumeration for maximum-degree-5 graphs and rules out polynomial delay on bipartite graphs of degeneracy 2 and maximum degree 6 unless P = NP.It also gives an FPT-delay algorithm parameterized by neighborhood diversity and rules out OutputFPT enumeration parameterized by pathwidth.Source: §1 · p. 2

• For a relation A, Enum A takes an input x and must output every y paired with x, without duplicates.The section assumes outputs are polynomially balanced in the input size.Source: §2 · p. 2
• Output-polynomial time bounds total runtime by a polynomial in both the input size and the number of outputs.OutputP is the class of enumeration problems admitting such an algorithm.Source: §2 · pp. 2–3
• Polynomial delay bounds the time between consecutive outputs and the intervals before the first and after the last output by a polynomial in input size.DelayP is contained in OutputP.Source: §2 · p. 3
• OutputFPT allows total runtime to include a computable parameter-dependent factor times a polynomial in input and output size.The section defines DelayFPT analogously to polynomial delay.Source: §2 · p. 3

3 Enumeration with Maximum Degree at most 5

• For the parameterizations considered, the paper does not require the parameterization function to be polynomial-time computable.The stated reason is that some parameterizations considered in the paper would not meet that requirement.Source: §3 · p. 3
• Such alliances are single pendant vertices, induced paths with degree-2/3 endpoints and degree-4/5 internal vertices, or induced cycles with at most one vertex of degree below 4.These are the three distinct cases used by the algorithm.Source: §3 · pp. 3–4
• A polynomial-delay algorithm enumerates all inclusion minimal defensive alliances on graphs with maximum degree 5.The construction reduces the task to enumerating paths and cycles.Source: §3 · pp. 3–4
• The path and cycle cases can be enumerated using polynomial-delay algorithms for paths and cycles, while the singleton case requires enumerating degree-1 vertices.For paths, the algorithm considers endpoint pairs; for cycles, it handles cycles with a degree-2/3 vertex separately from cycles wholly in the degree-4/5 vertex set.Source: §3 · pp. 4–5

4 Another Inclusion Minimal Defensive Alliance

• Unless P = NP, no output-polynomial algorithm enumerates all inclusion minimal defensive alliances even on bipartite graphs of degeneracy 2 and maximum degree 6.Source: §4 · p. 5
• The paper describes a sharp boundary between maximum degree 5 and 6, and between degeneracy 1 and degeneracy 2 or larger.Forests have degeneracy 1.Source: §4 · p. 5
• Another Inclusion Minimal Defensive Alliance asks whether a graph has an inclusion minimal defensive alliance outside a supplied list.An output-polynomial enumeration algorithm would place this decision problem in P.Source: §4 · pp. 5–6
• The associated decision problem is NP-complete, even on bipartite graphs of degeneracy 2 and maximum degree 6.The reduction starts from Monotone 3-Sat-(2,2), where each variable occurs twice positively and twice negatively and clauses are all positive or all negative.Source: §4 · p. 6

4.1 Details of the proof of Theorem 9

• The reduction constructs a bipartite graph of maximum degree 6 and degeneracy 2, with the supplied list assembled from pendant singletons, components, and specified three-vertex alliances.Source: §4.1 · pp. 7–8
• The constructed instance has an alliance outside the list exactly when the Monotone 3-Sat-(2,2) formula is satisfiable.The claim supplies the reduction's correspondence between solutions and satisfying assignments.Source: §4.1 · p. 8

5.1 Neighborhood Diversity

• The neighborhood-diversity algorithm encodes class occupancies in an ILP and uses minimality conditions to ensure its solutions correspond to inclusion minimal alliances.For each class support, it enumerates ILP solutions with FPT-delay and then enumerates the alliances corresponding to each solution with polynomial delay.Source: §5.1 · pp. 10, 11, 13, 14
• All inclusion minimal defensive alliances can be enumerated with FPT-delay when parameterized by neighborhood diversity.The algorithm considers at most 2^nd class supports, uses an integer linear program for each, and enumerates alliances corresponding to each solution with polynomial delay.Source: §5.1 · pp. 10, 14
• The neighborhood-diversity result also yields FPT-delay enumeration parameterized by vertex cover number.This is stated as a corollary of the neighborhood-diversity theorem.Source: §5.1 · pp. 10, 14

5.2 Treewidth

• tw-AnIMDefAll is W[1]-hard even on graphs with degeneracy 2, ruling out FPT-delay enumeration parameterized by treewidth unless FPT = W[1].The proof reduces from the W[1]-hard Minimum Maximum Outdegree problem and constructs a graph whose treewidth is at most the source graph's treewidth plus 5.Source: §5.2 · pp. 14–15
• The reduction constructs a 2-degenerate graph G′ with an inclusion minimal defensive alliance outside L′ exactly when (G, r) is a yes-instance of MinMaxOut.Source: §5.2 · pp. 16–17
• Theorem 20 states that no OutputFPT algorithm can enumerate inclusion minimal defensive alliances parameterized by treewidth, unless FPT ≠ W[1], even on graphs of degeneracy 2.Source: §5.2 · p. 18
• To the authors’ knowledge, Lemma 19 is the first use of a parameterized Another-problem variation to obtain this kind of non-enumerability result.Source: §5.2 · p. 19
• There is no OutputFPT algorithm for enumerating inclusion minimal defensive alliances parameterized by pathwidth unless FPT = W[1], even on graphs of degeneracy 2.The paper establishes W[1]-hardness for pw-MinMaxOut as part of this result.Source: §5.2 · pp. 19–20

6 Conclusions

• Non-monotonicity makes alliance problems escape many metatheorems because it cannot be expressed in monadic second-order logic.The authors also identify offensive and powerful alliances as directions for future enumeration research.Source: §6 · p. 20
• Extension inclusion minimal defensive alliance is NP-complete on bipartite graphs of degree at most 6 and degeneracy 2.The reduction makes a specified pre-solution extendable exactly when the formula is satisfiable.Source: §6 · p. 20
• Parameterized by pre-solution size, extension is para-NP-complete; treewidth-parameterized extension is W[1]-hard even at degeneracy 2.Source: §6 · p. 21
• Neighborhood-diversity-parameterized extension is in FPT, using the enumeration theorem’s ILP with lower bounds for the pre-solution.The ILP’s variable count is bounded by a function of neighborhood diversity.Source: §6 · p. 21
• Whether XP-delay enumeration is possible for treewidth or pathwidth remains open; vertex integrity and twin-cover are also suggested parameters.Source: §6 · pp. 20–21