[Rule] MaximumAcyclicAgreementForest to MinimumFeedbackVertexSet

[zhangjieqingithub]

Companion rule for the model proposal in #1046.

Source / Target

• Source: MaximumAcyclicAgreementForest (default variant) — see [Model] MaximumAcyclicAgreementForest #1046
• Target: MinimumFeedbackVertexSet (directed graph, weight i32)

Motivation

This is the canonical structural reduction from hybridization number to directed feedback vertex set ("Cycle Killer", van Iersel–Kelk–Lekić–Scornavacca 2012). It

• connects MaximumAcyclicAgreementForest to the existing MinimumFeedbackVertexSet hub and transitively to the ILP/QUBO clusters;
• preserves the optimum exactly: the hybridization number of $(T_1, T_2)$ equals the minimum DFVS size of the constructed auxiliary digraph; and
• establishes a 2-approximation bridge (DFVS is 2-approximable on the auxiliary graph, yielding a 2-approximation for hybridization).

Reference

Van Iersel, Kelk, Lekić, Scornavacca, "Cycle Killer…Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set", SIAM Journal on Discrete Mathematics 26(4), 2012. https://epubs.siam.org/doi/10.1137/120864350

Reduction Algorithm

Let $T_1, T_2$ be the input rooted binary phylogenetic trees on leaf set $X$, $n = |X|$.

1. Kernelization (optional but standard). Apply the subtree and chain reductions of Bordewich–Semple (2005) to $(T_1, T_2)$ exhaustively: collapse every maximal common pendant subtree to a single leaf, and replace every maximal common chain of length $\geq 3$ by a chain of length $3$. These reductions preserve hybridization number.
2. Build the display graph $D(T_1, T_2)$: the vertex-disjoint union of $T_1$ and $T_2$ with corresponding leaves identified, plus both roots as sources.
3. Construct the auxiliary digraph $H$. Following §4 of van Iersel et al., introduce one vertex of $H$ for each edge-pair $(e_1, e_2) \in E(T_1) \times E(T_2)$, plus one vertex for each leaf $\ell \in X$. Add a directed arc $u \to v$ between auxiliary vertices whenever the corresponding edge-pairs induce an ancestor relation on their common leaf set in $D(T_1, T_2)$.
4. Reduce. Return MinimumFeedbackVertexSet on $H$ with unit weights $w \equiv 1$.

Solution lifting. A minimum feedback vertex set $S \subseteq V(H)$ determines a minimum set of edge-pairs whose removal makes the ancestor digraph acyclic; the connected components of the cut $D(T_1, T_2)$ form a maximum acyclic agreement forest $F$ with $|F| = |S| + 1$.

Size Overhead

Target size fields from pred show MinimumFeedbackVertexSet → size_fields = [num_arcs, num_vertices].

Field	Formula
num_vertices	num_leaves ^ 2
num_arcs	num_leaves ^ 3

(After kernelization the effective sizes are bounded by a function of the hybridization number $k$, but the worst-case formulas above express the raw construction.)

Validation Method

Closed-loop test: construct the source instance, apply the reduction, solve the target by brute force, lift the solution, and check that the recovered $F$ is (a) a valid acyclic agreement forest of $(T_1, T_2)$ and (b) $|F| - 1$ matches the ground-truth hybridization number.

Example (fully worked)

Source. $X = {a, b, c, d}$, $T_1 = ((a,b),(c,d))$, $T_2 = ((a,c),(b,d))$ (the 4-leaf quartet swap).

Construction. No pendant subtree or chain is common, so kernelization does nothing. $T_1$ and $T_2$ each have 6 edges (3 internal + 3 leaf-edges after root edges are dropped). The auxiliary digraph $H$ has $6 \cdot 6 + 4 = 40$ vertices and roughly $6^3 = 216$ arcs (upper bound).

Target solved. Minimum DFVS size of $H$ is $|S| = 3$.

Lifted solution. $|F| = |S| + 1 = 4$, and the only acyclic agreement forest achieving this is $F = {{a},{b},{c},{d}}$. Hybridization number = 3.

BibTeX

@article{vanIerselKLS2012,
  author  = {van Iersel, Leo and Kelk, Steven and Leki\'{c}, Nela and Scornavacca, Celine},
  title   = {Cycle Killer\ldots Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set},
  journal = {SIAM Journal on Discrete Mathematics},
  volume  = {26},
  number  = {4},
  pages   = {1635--1656},
  year    = {2012},
  doi     = {10.1137/120864350},
}

@article{BordewichS2005,
  author  = {Bordewich, Magnus and Semple, Charles},
  title   = {On the computational complexity of the rooted subtree prune and regraft distance},
  journal = {Annals of Combinatorics},
  volume  = {8},
  number  = {4},
  pages   = {409--423},
  year    = {2005},
  doi     = {10.1007/s00026-004-0229-z},
}