In a directed graph (a graph whose edges have orientations), there is a classical trade-off between two quantities. One is how many cycles you can pack so that they share no vertex. The other is how few vertices you must delete to destroy every cycle. For vertex-disjoint packings, the best known relationship between them is a tower of exponentials. It becomes a small polynomial once each vertex may lie on up to four cycles (a "quarter-integral" packing): Packing Directed Cycles Quarter- and Half-Integrally shows that a digraph without $k$ such cycles has a deletion set of size $O(k^4)$. The same authors ask whether a near-linear bound $O(k \cdot \mathrm{polylog}\, k)$ is possible. Their proof goes through directed treewidth and path systems, and a quadratic loss in one lemma blocks progress.
We propose a different route to that question. First solve the linear-programming relaxation, which asks for a fractional cycle packing: cycles get weights, and weights through each vertex sum to at most 1. Then round it to an integral packing in which each vertex lies on at most $c$ cycles, losing only a polylogarithmic factor. The rounding is a "nibble," in the sense of the iterative partial coloring literature: a process that commits a small random fraction of choices per round and re-balances the rest so that no vertex's remaining capacity is used up too fast. When the nibble stalls, we aim to show the stall itself exposes a region of high directed treewidth. Known structural results can harvest a packing directly from that region. The fractional packing number is already known to be near-linear in the deletion number, by Seymour's fractional result for directed cycles, which is outside this file. A rounding with polylog loss would therefore give the near-linear quarter-integral bound. It would also give a polynomial-time algorithm for all $k$, not only fixed $k$.
Core Claim
The obstruction to rounding is specific and measurable, and it is the same obstruction the structural theory handles. Write $A$ for the vertex-by-cycle incidence matrix and $x$ for a fractional packing with $Ax \le 1$ and total weight $\nu^*$. We seek $y \in \{0,1\}^{\text{cycles}}$ satisfying
$$Ay \le c \cdot \mathbf{1}, \qquad \mathbf{1}^\top y \ge \nu^* / \mathrm{polylog}(\nu^*),$$
for a constant $c \in \{2,4\}$. Short cycles are easy. With cycle length bounded by $\ell$, each column of $A$ has at most $\ell$ nonzeros, so conflicts are local and standard nibble and local-lemma arguments apply. Long cycles are the problem. A vertex can sit on many long cycles that each touch many other vertices, so dependencies are unbounded. One-shot sampling at rate $1/L$ then needs $L \approx n^{1/c}$ to control every vertex's load by a union bound.
Our claim is a dichotomy. Run a multi-round nibble that re-solves the fractional packing on the residual capacities after each round, and track a smoothed maximum load. Then either the rounding loses only polylog factors, or the set of vertices where the potential spikes carries a large well-linked system of long overlapping cycles. That set has directed treewidth polynomial in the stalled mass. The fallback is then the high-treewidth packing theorem of Packing Directed Cycles Quarter- and Half-Integrally, which extracts a quarter-integral packing directly.
The target has two tiers. The realistic goal is any quarter-integral bound below $O(k^4)$ with a polynomial-time algorithm. The stretch goal is $O(k\,\mathrm{polylog}\,k)$.
Where This Sits
Three lines of work supply the ingredients, and each plays a different role.
The motivating gap comes from the structural papers. Packing Directed Cycles Quarter- and Half-Integrally (also Packing directed circuits quarter-integrally) obtains $O(k^4)$, $O(k^5)$ and $O(k^6)$ for congestion 4, 3 and 2. It works purely with linkages and a partitioning lemma for dense intersection graphs, and never uses the fractional relaxation. Constant congestion brambles in directed graphs proves that directed treewidth $O(k^{48}\log^{13}k)$ forces a congestion-8 bramble, meaning a family of mutually touching strongly connected pieces. It uses the Lovász Local Lemma in the sparse case, so it is non-constructive there. We reuse both as fallbacks rather than as the main engine. That is the main difference from the closest prior work: they build packings from treewidth, while we build them from the LP and turn to treewidth only when rounding fails.
The rounding method comes from the nibble and discrepancy literature. Near-Optimal, Distributed Edge Colouring via the Nibble Method keeps each vertex's remaining palette concentrated by coloring a small fraction of edges per round. We use the same idea, with a vertex's remaining cycle capacity playing the role of the palette. Spectral Sparsification by Deterministic Discrepancy Walk steers a walk with a smoothed-maximum potential and restricted update directions. We adapt the scalar version to derandomize the nibble. The potential is
$$\Phi = \sum_v \exp(\lambda\, \mathrm{load}_v),$$
where $\mathrm{load}_v$ is the number of chosen cycles through vertex $v$ and $\lambda$ controls the smoothing. Fast Discrepancy Minimization with Hereditary Guarantees projects out heavy rows before partial coloring, and we borrow that move: vertices whose potential spikes are frozen and handed to the structural fallback. Packing Cycles Faster Than Erdos-Posa motivates separating short from long cycles through a small set hitting short cycles, but it is undirected and exact-FPT, so it constrains our design without supplying it.
The constraints come from the negative results. Vertex-disjoint packing of directed odd cycles fails the trade-off entirely (A half-integral Erdős-Pósa theorem for directed odd cycles), so our $c=1$ experiments serve only as a reference. Any route through The Directed Grid Theorem reintroduces the tower, so our fallback must use the polynomial bramble and packing results and never the grid theorem.
Research Program
The analytic work has three parts.
The first is the short-cycle regime. For fractional mass on cycles of length at most $\ell$, we will prove that the residual-re-solving nibble outputs a $c$-congested packing of size $\Omega(\nu^*_{\le \ell}/\mathrm{poly}(\ell))$ deterministically. The deterministic version uses $\Phi$ to choose each round's batch, in the style of the discrepancy walk.
The second part is the crux: a stall lemma. If a round's potential increase exceeds its budget, the heavy vertices span many long cycles with pairwise intersections in a controlled pattern. We will then try to show that this pattern contains a well-linked set of size polynomial in the stalled mass, and hence high directed treewidth. We expect the analysis to mirror the dense/sparse split of Constant congestion brambles in directed graphs. The difference is that the objects are LP-weighted cycles rather than threaded linkages, and the weights may let us avoid the quadratic blow-up of their Lemma 7.
The third part is accounting. Fallback invocations each consume vertex mass. We must bound how many rounds end in a stall, so that the total loss is a product of polylog nibble losses and a bounded number of polynomial fallback losses. If the fallback's polynomial loss compounds, the stretch goal fails, but a sub-quartic bound may survive.
A secondary thread tests transfer to directed odd cycles. The fractional odd-cycle packing LP has a polynomial separation oracle, namely shortest odd closed walks in a parity-doubled graph. The rounding stage therefore carries over unchanged, and only the stall lemma would need parity-breaking arguments like those in A half-integral Erdős-Pósa theorem for directed odd cycles. This is where a polynomial half-integral bound for odd cycles could come from without the grid theorem. We treat it as exploratory.
Alongside the proofs we will build an implementation, used to measure the empirical rounding loss before investing in proofs of the stall lemma. It solves the fractional packing by column generation, where the pricing step is a minimum-weight directed cycle, and then runs the nibble variants.
Baselines
The naive reference is greedy disjoint packing. It repeatedly finds a shortest directed cycle, records it, deletes its vertices, and stops when the graph is acyclic; for $c>1$ it deletes a vertex only once $c$ chosen cycles pass through it. It uses no LP and costs almost nothing. The proposal must beat it by a clear margin on packing size to justify the LP.
The strongest simple rounding competitor is independent sampling with alteration. Starting from the same fractional solution $x$, it samples each cycle with probability $x_C/L$, drops cycles through overloaded vertices, and tunes $L$ per instance over the same grid of values and the same wall-clock budget as our nibble. A resampling variant, which repeatedly resamples cycles through violated vertices until none remain, represents the constructive-local-lemma approach. Our method beats these baselines if it achieves a smaller ratio $\nu^*/\nu_c$ at equal $c$, where $\nu_c$ is the size of the congestion-$c$ packing found. More importantly, that ratio should grow no faster than polylogarithmically in $\nu^*$ on the families where theirs grows polynomially.
On the theory side, the strongest existing result is the $O(k^4)$ quarter-integral bound of Packing Directed Cycles Quarter- and Half-Integrally, with $O(k^6)$ for congestion 2. Beating it means a proven smaller exponent. There is no implemented version of their construction to run, and we will not pretend to compare against one empirically.
For the upper side of the trade-off, the deletion sets, the strongest reference is TRSA from Threshold-Based Responsive Simulated Annealing for Directed Feedback Vertex Set Problem. It reports a total gap of 0.4% to the best results of all algorithms on the 100 PACE 2022 heuristic instances, with best results on 92 of them. Across all 140 instances it improved the best known results on 53 and matched them on 79 more. We will use the best-known deletion sets as $\tau$ rather than competing with them. Where the exact track resolves instances, as with PACE Solver Description: DAGer - Cutting out Cycles with MaxSAT, we use those optima. We found no reported result on Lacuna for constant-congestion cycle packing sizes on any DFVS benchmark, so the packing side has no published number to beat.
Three ablations isolate the key ingredients. The first removes residual re-solving and nibbles from a fixed $x$. The second replaces the potential-guided batch with uniform-rate sampling. The third disables the stall fallback. If the ablation without re-solving matches the full method, the "palette shock" analogy is not doing the work, and we would drop it from the theory.
Why not just…?
Why not just make the Masarík et al. local-lemma step constructive with resampling? This would plausibly give an algorithm for their existing bounds. It would not touch the exponents, which is our main target. We include the resampling rounding as a baseline for exactly this reason. If it matches our nibble's empirical loss on long-cycle families, the rounding contribution collapses. What would remain is a stall-lemma question that has to be judged purely on its bound.
Why not just use independent randomized rounding with alteration? The union bound over vertices forces a sampling rate of about $n^{-1/c}$ when a vertex lies on many long cycles, which is a polynomial loss in $n$ rather than in $k$. On instances where cycles are short this baseline may be competitive, and we expect it to be. The decisive test is the long-cycle synthetic families and cylindrical-wall-like constructions, where we predict it degrades and the nibble does not.
Why not just sharpen Lemma 7 of the quarter-integral paper directly? This is a real threat. A purely combinatorial improvement to that lemma could beat $O(k^4)$ with no LP at all. Our response is that the LP route also yields polynomial-time algorithms for all $k$. Its fractional weights also supply averaging that linkage arguments lack. If the stall lemma ends up reproducing Lemma 7's loss, we will report that the LP gives no advantage.
Why not just use the fractional LP value as a lower-bound certificate for solvers? It already is the stronger certificate: any congestion-$c$ packing of size $m$ certifies only $\tau \ge m/c$, which never exceeds $\nu^*$. We do not claim better dual bounds for PACE solvers. The computational work measures the empirical trade-off function, not certificates.
Proposed Experiments
We will use three benchmark sets: the 100 PACE 2022 heuristic-track instances, the 40 classical public DFVS instances used by Threshold-Based Responsive Simulated Annealing for Directed Feedback Vertex Set Problem, and the controlled random generator of Experimental Study of FPT Algorithms for the Directed Feedback Vertex Set Problem. The generator sweeps size $n$, edge density, and planted deletion-set size $k$. We will add directed-grid and cylindrical-wall families with growing radius, where long overlapping cycles dominate. For each instance and $c \in \{1,2,4\}$ we record five quantities: $\nu^*$, $\nu_c$ from each method, $\tau$ (best known), the rounding loss $\nu^*/\nu_c$, and the empirical trade-off ratio $\tau/\nu_c$.
The first decisive check fits the rounding loss against $\nu^*$ on the scalable families. Polylog growth for the full nibble and polynomial growth for independent sampling would support the core claim. Matching growth for the two would refute the claim that the nibble is necessary.
The second check logs where stalls occur and computes directed-treewidth lower bounds, via well-linked-set witnesses, on the stalled vertex sets. If stalls do not concentrate on high-treewidth regions, the stall lemma is likely false as stated, and we would redirect before attempting a proof.
The third check plots $\tau/\nu_4$ against $\tau$ across all instances. A near-linear empirical trend is consistent with the conjectured $O(k\,\mathrm{polylog}\,k)$ bound, and a clearly super-linear trend on structured families would temper the stretch goal. These experiments cannot prove any bound. What they do is decide cheaply whether the dichotomy is worth proving.
References
- Packing Directed Cycles Quarter- and Half-Integrally
- Packing Directed Circuits Quarter-Integrally
- Constant Congestion Brambles in Directed Graphs
- Near-Optimal, Distributed Edge Colouring via the Nibble Method
- Spectral Sparsification by Deterministic Discrepancy Walk
- Fast Discrepancy Minimization with Hereditary Guarantees
- Packing Cycles Faster Than Erdos-Posa
- A half-integral Erdős-Pósa theorem for directed odd cycles
- The Directed Grid Theorem
- Threshold-Based Responsive Simulated Annealing for Directed Feedback Vertex Set Problem
- PACE Solver Description: DAGer - Cutting out Cycles with MaxSAT
- Experimental Study of FPT Algorithms for the Directed Feedback Vertex Set Problem