Pith. sign in

REVIEW 27 references

Reviewed by Pith at T0; open to challenge.

T0 means a machine referee read the full paper against a public rubric. The mark states how deep the mechanical check went, never who wrote it. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · glm-5.2

Beating the spanning-tree bound for acyclic subgraphs

2026-07-09 01:28 UTC pith:RFBYOUXV

load-bearing objection Two new above-guarantee results for weighted MAS above the MaxST bound — an FPT algorithm for integer weights and an XP algorithm for rational weights. The proofs are intricate and carefully structured; I could not find a logical gap in the main arguments.

arxiv 2607.07705 v1 pith:RFBYOUXV submitted 2026-07-08 cs.DS

Exploiting Spanning Trees for Directed Acyclicity

Sergei Khargeliia , Danil Sagunov This is my paper
classification cs.DS
keywords weightacyclicmathcalweightsdirectededgemaxstrational
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the Maximum Acyclic Subgraph (MAS) problem on directed graphs with edge weights. Any directed graph always contains an acyclic subgraph whose weight is at least that of its maximum spanning tree (MaxST) — the heaviest spanning tree of the underlying undirected graph. The authors ask: given an integer k, can we find an acyclic subgraph of weight at least MaxST(G) + k, or prove none exists? They give two parameterized algorithms that answer this question. For integer edge weights, the algorithm runs in 2^{k^{O(1)}} · |I|^{O(1)} time (FPT). For rational weights bounded below by 1, the algorithm runs in n^{k^{O(1)}} · |I|^{O(1)} time (XP). The positive result for rational weights is notable because beating the weaker random-ordering bound (half the total edge weight) by even +1 is NP-hard in the same rational-weight setting. The central mechanism is a classification of edges relative to the MaxST into tree edges, allowed edges (which can be added without creating cycles), and blocked edges (which create cycles). The key concept is the profit of a tree edge: the weight of blocked edges that become usable when that tree edge is removed, minus the weight of the tree edge itself. If enough tree edges have sufficient profit, their removal and replacement by unblocked edges yields a heavier acyclic subgraph. For integer weights, profits are integers, so only k^{O(1)} distinct profit values matter, enabling bounded branching. For rational weights, profits can be arbitrarily small, so the authors instead exploit the fact that the conflict graph between tree edges (where two edges conflict if they share a blocked edge) is a perfect graph, allowing maximum-weight independent set to be solved in polynomial time. They combine this with a compressed representation of acyclic subgraphs and a recursive constraint-set construction to handle allowed edges.

Core claim

The core discovery is that the MaxST lower bound for MAS admits above-guarantee parameterized algorithms in both integer and rational weight settings, despite the problem being NP-hard above the weaker random-ordering bound with rational weights. The mechanism is the profit-based trade of tree edges for their inverse edges, combined with the perfect-graph structure of the inverse-edge conflict graph for rational weights.

What carries the argument

The key machinery is the edge classification (tree/allowed/blocked), the profit and remaining-profit of tree edges, the decomposition of MaxST into directed paths with a proper path cover and P-respecting ordering, the reduction to Weighted Directed Feedback Arc Set for fixed removed-tree-edge sets, the proof that the inverse-edge conflict graph is perfect, and the constraint-set construction for forbidding directed paths in subgraphs of the form T−S+Inv(S).

Load-bearing premise

The FPT algorithm for integer weights relies on an external result that Weighted Directed Feedback Arc Set is solvable in 2^{O(k^8 log k)} · n^{O(1)} time, and the correctness of the overall algorithm depends on this result applying cleanly in the specific way Lemma 5 uses it — with both weight and cardinality bounds set to the same value k'.

What would settle it

Construct an instance of MAS/MaxST with integer weights where every tree edge has profit strictly between 0 and 1 (impossible with integer weights, but testable with rational weights) and the optimal solution requires removing more than k^{O(1)} tree edges — this would break the XP algorithm's enumeration bound.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The MaxST bound can serve as a parameterization baseline for other ordering problems on directed graphs, including variants of Max Cut and feedback set problems.
  • The perfect-graph property of the inverse-edge conflict graph may transfer to other problems where tree-edge conflicts arise from shared non-tree elements.
  • The gap between FPT (integer weights) and XP (rational weights) suggests a natural boundary: integrality of profits enables bounded branching, while rational profits require structural substitutes.
  • The constraint-set machinery for forbidding paths in T−S+Inv(S) subgraphs may be reusable in other above-guarantee algorithms on directed graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the open question of whether MAS/MaxST(Q≥1) is FPT or W[1]-hard is resolved positively, the perfect-graph and constraint-set machinery developed here would likely form the structural foundation for such an algorithm.
  • The MaxST bound could be combined with the Poljak–Turzík bound in a hybrid parameterization, since the two bounds are incomparable on sparse versus dense graphs — an algorithm that beats both simultaneously would need to handle both profit-based and connectivity-based structure.
  • The perfect-graph result on H_{G,w} might extend to conflict graphs arising from other spanning structures (e.g., arborescences in directed graphs), potentially enabling similar above-guarantee algorithms for problems like directed Steiner tree variants.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 0 minor

Summary. The paper studies the Maximum Acyclic Subgraph (MAS) problem parameterized above the maximum spanning tree (MaxST) guarantee. Given a weakly-connected edge-weighted digraph G and integer k, the task is to find an acyclic subgraph of weight at least w(MaxST(G)) + k or report that none exists. The MaxST lower bound is a natural but previously unexplored guarantee for MAS that dominates the random-ordering and Poljak–Turzík bounds on instances where edge weights concentrate around a sparse structure. The paper presents two main algorithmic results: (1) Theorem 1 — an FPT algorithm for integer weights running in 2^{k^{O(1)}} · |I|^{O(1)} time, and (2) Theorem 2 — an XP algorithm for rational weights ≥ 1 running in n^{k^{O(1)}} · |I|^{O(1)} time. The FPT algorithm combines a structural decomposition of MaxST into directed paths (Lemma 3), a greedy-like branching strategy based on remaining profits (Lemma 4), and a reduction to Weighted Directed Feedback Arc Set (Lemma 5, using [KKPW25]). The XP algorithm replaces profit classification with a perfect-graph-based maximum-weight independent set approach (Lemma 6 shows H_{G,w} is perfect via the Strong Perfect Graph Theorem) and an intricate constraint-set construction for handling allowed edges (Lemmas 7–10).

Significance. This is a substantial contribution to above-guarantee parameterized complexity, particularly notable for being one of the few positive results for a weighted problem on directed graphs with rational weights. The MaxST lower bound is a natural and well-motivated guarantee that has been overlooked in prior work. The structural insights are deep and independently interesting: Lemma 6 (the conflict graph H_{G,w} is perfect) is a clean graph-theoretic result, and Lemma 9 (forbidding directed paths via constraint sets with a recursive construction and potential-function analysis) is technically sophisticated. The black-box usage of external results — Proposition 1 (order dimension of oriented tree posets, [TM77, AS26]), Proposition 2 (WDFAS FPT algorithm, [KKPW25]), Proposition 3 (Strong Perfect Graph Theorem, [CRST06]), and Proposition 4 (MWIS in perfect graphs, [GLS81]) — is standard and well-justified. The open questions in Section 6 (FPT vs. W[1]-hardness for rational weights, kernelization, extension to Poljak–Turzík bound) are well-posed and will stimulate further research.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and the positive assessment. The referee's summary accurately captures the main results, the structural insights, and the role of the external results we use. As the referee notes, the MAJOR COMMENTS section is empty, so there are no specific points requiring a detailed response. We will use the opportunity to do a thorough proofreading pass and tighten the presentation before the next version.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper derives two parameterized algorithms for Maximum Acyclic Subgraph above the MaxST bound. The derivation chain is self-contained against external benchmarks. The main theorems (Theorem 1 and Theorem 2) are built from the paper's own structural lemmas (Lemmas 1-10) combined with four externally cited results: Proposition 1 (Trotter-Moore [TM77], Abram-Segovia [AS26]) for poset dimension, Proposition 2 (Kim-Kratsch-Pilipczuk-Wahlström [KKPW25]) for WDFAS FPT algorithm, Proposition 3 (Chudnovsky-Robertson-Seymour-Thomas [CRST06]) for the Strong Perfect Graph Theorem, and Proposition 4 (Grötschel-Lovász-Schrijver [GLS81]) for maximum-weight independent set in perfect graphs. All four are standard black-box usages of independent results by different author sets. No 'prediction' is equivalent to a fitted input. The paper's own definitions (profit, remaining profit, inverse edges, Inv-respecting subgraphs, constraint sets) are introduced as structural tools and their properties are proved from first principles within the paper. The reduction in Lemma 5 from the fixed-S subproblem to WDFAS is a straightforward transformation where the dual instance I'=(X,w',k',k') is constructed from the graph structure, not from a fitted parameter. The branching in Algorithm 1 covers cases derived from Lemma 4's three modification types, each proved independently. No self-citation chain is load-bearing for the central claims.

Axiom & Free-Parameter Ledger

1 free parameters · 5 axioms · 4 invented entities

The paper introduces several definitions (profit, remaining profit, inverse edges, constraint sets) but all are derived from the input graph structure without free parameters. The only input parameter is k. External results are standard or from peer-reviewed literature. No circular dependencies detected.

free parameters (1)
  • k
    The parameter k is the input to the problem, not a fitted constant. It represents the target excess weight above MaxST.
axioms (5)
  • standard math MaxST(G,w) is a valid lower bound for MAS (any spanning tree is acyclic)
    Used throughout; a tree has no cycles, so it is a feasible acyclic subgraph.
  • standard math Order dimension of oriented tree posets is at most 3 (Proposition 1, [TM77, AS26])
    Invoked in Lemma 2 to partition allowed edges into 3 acyclic classes. External result with polynomial-time construction.
  • domain assumption WDFAS is FPT (Proposition 2, [KKPW25])
    Invoked in Lemma 5 to solve the fixed-S subproblem. External result; correctness of Theorem 1 depends on it.
  • standard math Strong Perfect Graph Theorem (Proposition 3, [CRST06])
    Invoked in Lemma 6 to prove H_{G,w} is perfect by excluding odd holes and antiholes.
  • standard math Maximum-weight independent set in perfect graphs is polynomial (Proposition 4, [GLS81])
    Invoked in Lemma 7 to find maximum-profit S under constraints.
invented entities (4)
  • Tree edge profit p(e) = w(Inv(e)) - w(e) independent evidence
    purpose: Measures the net weight gain from removing tree edge e and adding all its inverse edges
    Falsifiable: if p(S) >= k for some S, then a solution of weight >= MaxST+k exists (Observation 4). The profit is computed from the graph, not fitted.
  • Remaining profit rp(S,e) = w(Inv(e)∖Inv(S)) - w(e) independent evidence
    purpose: Tracks actual marginal profit when some tree edges are already removed
    Derived from profit definition; used in Lemma 4 to bound branching choices.
  • Inverse edge (Definition 3) independent evidence
    purpose: A blocked edge b is inverse to tree edge e if T-e+b is acyclic
    Structural definition with no free parameters; determines which non-tree edges become available when tree edges are removed.
  • Constraint sets (Section 5.2.3) independent evidence
    purpose: Collections of restriction triples (F,R,B') that characterize subgraphs avoiding forbidden directed paths
    Constructed algorithmically from the graph structure; used in the XP algorithm to handle allowed-edge interactions.

pith-pipeline@v1.1.0-glm · 50061 in / 2483 out tokens · 331828 ms · 2026-07-09T01:28:50.991811+00:00 · methodology

0 comments
read the original abstract

We study the weighted case of the \textsc{Maximum Acyclic Subgraph (MAS)} problem, where each edge of a given directed graph has a positive weight assigned, and the task is to find a maximum-weight acyclic edge set. The famous and well-studied random ordering lower bound guarantees the existence of an acyclic set that gives at least the half of the total edge weight. The maximum spanning tree (MaxST) guarantee, which is the weight of a maximum-weight acyclic subgraph of the underlying undirected graph of $G$, is another natural lower bound for the weight of an acyclic subgraph. A solution of this weight dominates the random ordering solution on instances where MaxST spans the most of the total edge weight. Our main contribution are two parameterized algorithms that find acyclic subgraphs of total weight larger than the weight of the MaxST of $G$. Both our algorithms find a solution of total weight at least $MaxST(G)+k$, for a given integer $k\ge 0$, or report that it does not exist, and first of our algorithms runs in time $2^{k^{\mathcal{O}(1)}}\cdot \mathcal{I}^{\mathcal{O}(1)}$ and works when all weights are integers; our second algorithm handles rational weights not less than $1$, and its running time is upper-bounded by $n^{k^{\mathcal{O}(1)}}\cdot \mathcal{I}^{\mathcal{O}(1)}$. This positive result is rather surprising since solving \textsc{MAS} above the random ordering lower bound is \classNP-hard in the same rational weights scenario, when $k=1$. Our findings unravel intricate connections between structure of MaxSTs and directed cycles, use perfect graph theorem to tackle rational weights, and raise graph-theoretic questions that are interesting on their own. Of another importance, this is one of the few examples of positive ``above guarantee'' results for a weighted problem on directed graphs, especially for rational weights.

Figures

Figures reproduced from arXiv: 2607.07705 by Danil Sagunov, Sergei Khargeliia.

Figure 1
Figure 1. Figure 1: (a) An instance with six tree edges (thick black), four allowed edges (green) and four [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Flow-augmentation I: Directed graphs , year =

    Kim, Eun Jung and Kratsch, Stefan and Pilipczuk, Marcin and Wahlstr\". Flow-augmentation I: Directed graphs , year =. J. ACM , month = jan, articleno =. doi:10.1145/3706103 , abstract =

    work page doi:10.1145/3706103

  2. [2]

    IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) , pages =

    Crowston, Robert and Gutin, Gregory and Jones, Mark , title =. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) , pages =. 2012 , volume =. doi:10.4230/LIPIcs.FSTTCS.2012.400 , annote =

    work page doi:10.4230/lipics.fsttcs.2012.400 2012

  3. [3]

    Journal of Computer and System Sciences , volume=

    Parameterizing above or below guaranteed values , author=. Journal of Computer and System Sciences , volume=. 2009 , publisher=

    work page 2009

  4. [4]

    Theoretical Computer Science , volume=

    Parameterized algorithms for feedback set problems and their duals in tournaments , author=. Theoretical Computer Science , volume=. 2006 , publisher=

    work page 2006

  5. [5]

    Journal of Computer and System Sciences , volume=

    A probabilistic approach to problems parameterized above or below tight bounds , author=. Journal of Computer and System Sciences , volume=. 2011 , publisher=

    work page 2011

  6. [6]

    Beyond Max-Cut: -extendible properties parameterized above the Poljak--Turz

    Mnich, Matthias and Philip, Geevarghese and Saurabh, Saket and Such. Beyond Max-Cut: -extendible properties parameterized above the Poljak--Turz. Journal of Computer and System Sciences , volume=. 2014 , publisher=

    work page 2014

  7. [7]

    Discrete Mathematics , volume=

    A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound , author=. Discrete Mathematics , volume=. 1986 , publisher=

    work page 1986

  8. [8]

    Algorithmica , volume=

    Linear kernels and linear-time algorithms for finding large cuts , author=. Algorithmica , volume=. 2018 , publisher=

    work page 2018

  9. [9]

    Networks , volume=

    On the computational complexity of combinatorial problems , author=. Networks , volume=. 1975 , publisher=

    work page 1975

  10. [10]

    A survey on graph problems parameterized above and below guaranteed values , journal =

    Gregory Gutin and Matthias Mnich , keywords =. A survey on graph problems parameterized above and below guaranteed values , journal =. 2025 , issn =. doi:https://doi.org/10.1016/j.cosrev.2025.100795 , url =

    work page doi:10.1016/j.cosrev.2025.100795 2025

  11. [11]

    Graph theory , volume =

    Diestel, Reinhard , date-added =. Graph theory , volume =

    work page

  12. [12]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

    Marek Cygan and Fedor V. Fomin and Lukasz Kowalik and Daniel Lokshtanov and D. Parameterized Algorithms , url =. 2015 , bdsk-url-1 =. doi:10.1007/978-3-319-21275-3 , isbn =

    work page doi:10.1007/978-3-319-21275-3 2015

  13. [13]

    Annals of Mathematics , volume =

    Chudnovsky, Maria and Robertson, Neil and Seymour, Paul and Thomas, Robin , title =. Annals of Mathematics , volume =. 2006 , doi =

    work page 2006

  14. [14]

    The ellipsoid method and its consequences in combinatorial optimization , journal=

    Gr. The ellipsoid method and its consequences in combinatorial optimization , journal=. 1981 , month=. doi:10.1007/BF02579273 , url=

    work page doi:10.1007/bf02579273 1981

  15. [15]

    Algorithmica , month = apr, pages =

    Lill, Jonas and Petrova, Kalina and Weber, Simon , title =. Algorithmica , month = apr, pages =. 2025 , issue_date =. doi:10.1007/s00453-025-01306-y , abstract =

    work page doi:10.1007/s00453-025-01306-y 2025

  16. [16]

    Gutin and Viresh Patel , title =

    Gregory Z. Gutin and Viresh Patel , title =. 2016 , url =. doi:10.1137/140980946 , timestamp =

    work page doi:10.1137/140980946 2016

  17. [17]

    2007 , volume=

    Charikar, Moses and Makarychev, Konstantin and Makarychev, Yury , booktitle=. 2007 , volume=

    work page 2007

  18. [18]

    Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science , pages =

    Guruswami, Venkatesan and Manokaran, Rajsekar and Raghavendra, Prasad , title =. Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science , pages =. 2008 , isbn =. doi:10.1109/FOCS.2008.51 , abstract =

    work page doi:10.1109/focs.2008.51 2008

  19. [19]

    IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) , pages =

    Crowston, Robert and Fellows, Michael and Gutin, Gregory and Jones, Mark and Rosamond, Frances and Thomass\'. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) , pages =. 2011 , volume =. doi:10.4230/LIPIcs.FSTTCS.2011.229 , annote =

    work page doi:10.4230/lipics.fsttcs.2011.229 2011

  20. [20]

    , year =

    Crowston, Robert and Gutin, Gregory and Jones, Mark and Kim, Eun Jung and Ruzsa, Imre Z. , year =. Systems of Linear Equations over. doi:10.1007/978-3-642-13731-0_17 , booktitle =

    work page doi:10.1007/978-3-642-13731-0_17

  21. [21]

    and Gutin, G

    Crowston, R. and Gutin, G. and Jones, M. and Yeo, A. , year =. Parameterized Complexity of Satisfying Almost All Linear Equations over. Theory of Computing Systems , publisher =. doi:10.1007/s00224-012-9415-2 , number =

    work page doi:10.1007/s00224-012-9415-2

  22. [22]

    Theoretical Computer Science , pages=

    Computing minimum directed feedback vertex set in O*(1.9977 n) , author=. Theoretical Computer Science , pages=. 2007 , publisher=

    work page 2007

  23. [23]

    Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing , pages =

    Khot, Subhash , title =. Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing , pages =. 2002 , isbn =. doi:10.1145/509907.510017 , abstract =

    work page doi:10.1145/509907.510017 2002

  24. [24]

    American Journal of Mathematics , year =

    Partially Ordered Sets , author =. American Journal of Mathematics , year =. doi:10.2307/2371374 , url =

    work page doi:10.2307/2371374

  25. [25]

    The dimension of planar posets , journal =

    William T Trotter and John I Moore , abstract =. The dimension of planar posets , journal =. 1977 , issn =. doi:https://doi.org/10.1016/0095-8956(77)90048-X , url =

    work page doi:10.1016/0095-8956(77)90048-x 1977

  26. [26]

    2026 , eprint=

    Dimension of unicycle posets , author=. 2026 , eprint=

    work page 2026

  27. [27]

    Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound , journal =

    Lill, Jonas and Petrova, Kalina and Weber, Simon , keywords =. Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound , journal =. 2024 , copyright =. doi:10.4230/LIPICS.IPEC.2024.2 , url =

    work page doi:10.4230/lipics.ipec.2024.2 2024