{"id":"10137699-b254-4839-96da-16bea4366cd3","arxiv_id":"2512.25033","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"EF orientations are linear-time solvable for binary valuations but intractable for richer weights; those findings partially transfer to EFX orientations, with one key proof deferred.","lead":"This paper maps the computational difficulty of envy-free (EF) orientations on graphs, where edges are goods allocated to their endpoint agents. It gives a linear-time algorithm for binary valuations, hardness results for richer weights, and transfers some findings to the better-known EFX orientation problem.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central EFX treewidth algorithm (Theorem 23) is explicitly deferred to a future revision; the paper's headline progress on the Deligkas et al. open question rests on an unproved theorem.","rationale":"The reader's verdict of CONDITIONAL is appropriate: the paper has multiple plausible results, but the central EFX treewidth algorithm is missing its proof. The reader's weakest_assumption focused on the SETH parameter-counting gap in Theorem 9, which is a valid localized issue; however, the more load-bearing concern is the unproved Theorem 23, because it directly underpins the headline claim about the EFX open question. The manuscript itself flags the omission ('We will include it in a revised version'), so this is not an artifact of the review pipeline. Since the issue is a missing proof rather than a demonstrated counterexample, CONDITIONAL acceptance pending a complete proof is the right posture; the verdict should not be strengthened to REJECT or relaxed to ACCEPT. Thus the reader's CONDITIONAL verdict stands unchanged.","tokens_in":30551,"tokens_out":11612,"duration_ms":122420,"concrete_test":"Independently re-derive Theorem 23 from Theorem 14's framework: provide the full EFX-specific signature (revenue/demand with explicit flags for zero-goods and non-strong-envy) and prove the forget and join transition lemmas. If the re-derivation succeeds, the central claim stands; if a hidden obstruction appears (e.g., strong-envy demand cannot be summarized by a single W-bounded value across joins), Corollary 24 fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's strongest claim — that EFX ORIENTATION with polynomially-bounded weights is solvable in (n+m)^O(tw) time (Corollary 24) and hence nearly matches the ETH lower bound of Theorem 21 — depends entirely on Theorem 23. Yet Theorem 23 is stated with only a two-sentence sketch and the sentence: 'The proof is analogous to the proof of Theorem 14, albeit more complicated. We will include it in a revised version of this paper.' No complete proof is supplied. This is not a minor omission: EFX requires handling strong envy, which introduces qualitatively different conditions from EF — e.g., whether a vertex has received at least one good, and whether removing the last good from an envied bundle still triggers envy. The sketch's 'separately handling the case where a vertex has no received goods' is not a formal DP transition, and the forget/join lemmas corresponding to Lemmas 32 and 33 are absent. Consequently, Corollary 24, and the paper's claimed 'progress towards settling' the EFX open question, cannot be verified from the manuscript as written. The EF counterpart (Theorem 14) is far more fleshed out, but also lacks a fully formal proof; however, the load-bearing gap is the missing EFX DP proof. The SETH counting gap in Theorem 9 is real but less central and likely repairable by padding variables to force w_i >= 2.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies EF and EFX orientations in the graph model of Christodoulou et al. (2023), focusing on parameterized complexity. For EF orientations it gives a linear-time algorithm for binary valuations and its minimum-charity variant, multiple NP-hardness results (including weak NP-completeness for vertex cover number 2), W[1]/XNLP/XALP-hardness for polynomially bounded weights under vertex cover/pathwidth/treewidth, an FPT algorithm parameterized by the number of heavy edges with a claimed tight SETH lower bound, and a treewidth-based DP for polynomially bounded weights. The same treewidth DP is claimed for EFX orientations, and a reduction from EF to EFX transfers the hardness results, improving prior constants and giving a near-matching lower bound for the Deligkas et al. open question. The paper also introduces minimum-charity versions of both orientation problems.","tokens_in":30908,"tokens_out":14036,"duration_ms":136878,"significance":"If the EFX treewidth DP (Theorem 23) and the SETH lower bound (Theorem 9) were completed and correct, the paper would give an almost complete parameterized picture for EF and EFX orientations with polynomially bounded weights on bounded-treewidth/vertex-cover graphs. The EF side is supported by detailed appendix proofs for Theorems 5–14, and the EF-to-EFX reduction (Theorem 19) is clean, adding only two vertices. The paper uses standard external hardness assumptions (SETH, ETH, TARGETOUTDEGREEORIENTATION, 2P2N-3SAT) as black boxes, with no circularity or fitted parameters. However, the manuscript's headline EFX upper bound and the tightness of the heavy-edge lower bound are currently not established by the text.","major_comments":[{"comment":"The proof of Theorem 23 consists of a two-sentence sketch and ends with 'We will include it in a revised version of this paper.' This is an explicit deferral, not a proof. The EFX DP is not a routine variant of the EF DP: strong envy depends on v_i(X_j) - max_{e in X_j} v_i(e), not merely on the total value v_i(X_j), so a bag state storing one aggregate 'demand' per bag vertex is not evidently sufficient. The forget/join transitions corresponding to Lemmas 32–33 are absent. Since Corollary 24 and the claimed progress on the Deligkas et al. open question depend entirely on Theorem 23, the EFX upper-bound contribution cannot be verified from this manuscript.","section":"Section 4.2, Theorem 23 and Corollary 24"},{"comment":"The final paragraph claims that a (2-epsilon)^k algorithm for EF ORIENTATION would contradict SETH because the reduction produces at most n heavy edges and k <= n. However, w_i = max(#positive occurrences, #negative occurrences), so a variable appearing exactly once positively and once negatively has w_i = 1, and its {t_i, f_i} edge is not counted in k. Nothing in the reduction forces k = Omega(n); if k is small, (2-epsilon)^k is not (2-epsilon)^n. The proof needs an explicit padding/preprocessing step (or a proof that k = Omega(n)) before the SETH conclusion follows. The same issue does not affect Theorem 10, where variable edges have weight 2 by construction.","section":"Section 3.3, Theorem 9"}],"minor_comments":[{"comment":"The statement labeled 'Observation 4' is referred to as 'Theorem 4' in the paragraph before it and in the proof of Theorem 5. Please fix the cross-references.","section":"Section 3.1"},{"comment":"Claim 26 is cited as 'Theorem 26' in the proof. Also, the negation of Property 3 is described as 'an odd number of parallel edges'; it would be clearer to state explicitly that every parallel-edge pair has odd multiplicity and multiplicity at least 3.","section":"Appendix B, proof of Theorem 5"},{"comment":"The statement contains typos: '([O,W]^4 ...' should be '[0,W]^4'; the condition 'a^2_j <= r'(i) + sum a^1_i' appears to intend a sum over j in B_t of a^1_j; and the use of both i and j in the M_ij notation is confusing. Please proofread and clarify the indexing.","section":"Appendix B, Lemma 32"},{"comment":"The reference [Steihaus, 1948] should be 'Steinhaus'.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The main concern for the editor is that Theorem 23, on which the EFX treewidth DP and Corollary 24 rest, is explicitly deferred to a future revision; this is not a minor omission. The SETH gap in Theorem 9 is real but appears repairable with a padding argument. The EF results and the EF-to-EFX reduction are solid and form a strong core. I recommend major revision: the authors should supply a complete proof of Theorem 23 (or remove the EFX upper-bound claims), and fix the counting argument in Theorem 9."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is the first systematic study of EF orientations, and most of the EF-side results look right. The binary-valuation structural theorem (Theorem 5) is genuinely new and clean: it gives a linear-time algorithm for MIN-CHARITY EF ORIENTATION and generalizes the earlier simple-graph result to multigraphs. The heavy-edge FPT algorithm and the EF-to-EFX reduction are also solid additions; the reduction only adds two vertices and improves the known vertex-cover hardness constants from 8 to 4, which is a real improvement. Charity in the orientation model is a nice new direction.\n\nThe soft spots are localized but real. Theorem 23, the EFX treewidth DP, is not proved: the text says the proof is analogous to Theorem 14 but will be included in a revised version. Corollary 24 and the paper's headline progress on the Deligkas et al. open question rest entirely on that missing proof. This is not a cosmetic omission, because EFX's strong-envy condition changes the DP state space (whether a vertex has received any good, what happens when the last good is removed), and the forget/join lemmas are exactly where subtle errors hide. The EF counterpart in Theorem 14 is fleshed out in the appendix, so the authors know what a real proof looks like; they should supply the EFX version.\n\nThe SETH lower bound in Theorem 9 also has a counting gap. The reduction sets w_i = max(positive occurrences, negative occurrences), and when both are 1 the edge {t_i, f_i} is not heavy, so k can be much smaller than n. The final step only works if k = Ω(n); otherwise a (2−ε)^k algorithm does not contradict SETH. This looks repairable by padding each variable to force w_i ≥ 2, but as written the optimality claim for the heavy-edge parameterization does not follow.\n\nWho is this for? Researchers in fair division and parameterized complexity. The EF-side results are valuable and likely publishable; the EFX claims need revision. I would send this to peer review, but only with the explicit expectation that the authors either prove Theorem 23 or soften all claims that depend on it, and fix the parameter counting in Theorem 9.","headline":"Useful first map of EF orientations; the EF-side results are solid and new, but the EFX treewidth DP is explicitly deferred and the SETH lower bound has a parameter-counting gap.","tokens_in":31362,"tokens_out":1949,"would_cite":true,"duration_ms":24875,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68Q27","91B32"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper nearly settles the parameterized complexity of EF and EFX orientations for polynomially bounded weights, giving treewidth DP algorithms that match ETH lower bounds.","keywords":["EF orientation","EFX orientation","fair division","graph orientation","parameterized complexity","treewidth","vertex cover","charity"],"falsifier":"Find a formula with each variable appearing exactly once positively and once negatively, run the reduction of Theorem 9, and check whether the resulting k equals n; if k