{"id":"5c6f7168-e574-4ea7-bc1c-abc3abe371ee","arxiv_id":"2506.15379","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"EFX orientation with binary symmetric valuations stays easy on graphs one edge from bipartite and on P5-free or bounded-treewidth graphs, but becomes NP-complete at two edge-removals from bipartite or when P5 components appear.","lead":"This paper charts when a graph-based fairness rule, EFX orientation, can be solved efficiently. It shows the complexity is governed by how close the graph is to bipartite and by the shape of the value-1 subgraph.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's 2-SAT reduction silently discards 0-edges inside a single root-state neighborhood, turning infeasible root states into feasible ones; the P5-free tractability proof is incomplete as written.","rationale":"The reader's weakest-assumption was the inherited Proposition 8 from Zeng and Mehta. That characterization appears sound for binary symmetric additive instances and is not where I find the main risk. The load-bearing soft spot is internal to the paper's proof of Theorem 4, the P5-free tractability result: the reduction to 2-SAT mishandles 0-edges whose two endpoints both lie in the 1-neighborhood of a single root state. Such an edge makes that root state infeasible, but after the reconnection step it becomes a loop and is naturally discarded from a simple graph G0, so the infeasibility disappears and the 2-SAT instance can accept root choices that are not valid in the original instance. The small two-P3 example demonstrates this concretely: no EFX orientation exists, yet the reduction without loop clauses is satisfiable. This is not merely a presentation gap like the missing min-uncut computations or the unspecified choice in Theorem 12 Step 2; it directly affects the correctness of a headline algorithm. The fix is straightforward, namely keep loop-zero-edges as unit clauses, so the paper's overall direction is likely salvageable, but the proof as written does not establish Theorem 4. I therefore agree with the CONDITIONAL verdict but for a different, more substantive reason than the one given by the reader.","tokens_in":33744,"tokens_out":46498,"duration_ms":440723,"concrete_test":"Enumerate all small instances whose G1 is a disjoint union of one or two P3 or P4 trees with arbitrary 0-edges; for each, compare the output of the Theorem 4 2-SAT reduction as written (with loops removed) against a brute-force check of Proposition 8. Include the counterexample above: two P3 components with centers a,d and leaves b,c and e,f, with 0-edges bc, ad, ae, bd, cd. This instance has no EFX orientation, but the 2-SAT formula is satisfiable unless the bc loop is retained as a unit clause forbidding the center state. The test passes if the corrected reduction (loops converted to unit clauses) matches brute force on all such instances.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 5.3 and the appendix's 'Missing details of the proof of Theorem 4' reduce each P5-free tree to a single edge with two states. For a state u, all G0 edges with an endpoint in N1(u) are reconnected to the opposite new vertex v. If a G0 edge has both endpoints inside N1(u), both endpoints are replaced by v, producing a loop. The text does not say that such loops are kept as unit clauses; since G0 is defined as a simple subgraph, the most straightforward reading is that loops are discarded. That loses the constraint that root u is infeasible whenever N1(u) contains a G0 edge. Concretely, take two P3 components with centers a,d and leaves b,c and e,f, and add 0-edges bc, ad, ae, bd, cd. By Proposition 8 no rooting works: leaf/leaf is blocked by ad, leaf/center by ae, center/leaf by bd and cd, and center/center by bc, so the instance has no EFX orientation. The reduction with two states per P3 produces G0 edges that forbid three of the four root pairs but, after dropping the bc loop, leaves the center/center pair unconstrained; the resulting 2-SAT instance is satisfiable. The appendix's claim that 'the neighborhoods of the new states are the same' is exactly what fails for such internal 0-edges unless loop constraints are explicitly encoded.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the EFX-orientation problem for graphical fair division with symmetric additive valuations, building on the characterization of Zeng and Mehta. The main claims are: (1) binary instances whose graph has min-uncut number 1 are always solvable in linear time (Theorem 1); (2) the problem is NP-hard for binary instances with min-uncut number 2 and for instances with min-uncut number 1 when one edge is allowed to be non-binary (Theorem 2); (3) NP-completeness persists when every connected component of G1 is a P2, P3, or P5, G0 has maximum degree 1, and G is planar (Theorem 3); (4) the problem is linear-time solvable when every component of G1 is P5-free or cyclic (Theorem 4); (5) the problem is linear-time solvable on graphs of constant treewidth via an MSO formulation (Theorem 5); and (6) the number of large \"cores\" in G1 yields W[1]-hardness (Theorem 32). The proofs use Proposition 8 of Zeng and Mehta as the external characterization, standard algorithmic tools (2-SAT, Courcelle's theorem, min-uncut), and an internal decomposition into cores and split orientations.","tokens_in":33952,"tokens_out":11766,"duration_ms":118403,"significance":"If the results are correct, they substantially clarify the tractability frontier of EFX orientations: they show that min-uncut number 1 is tractable, min-uncut 2 is hard, and that induced P5s in the 1-edge graph are the essential obstruction for the binary case. The proposed core-based structural decomposition and the split-orientation gadgets are interesting and novel, and the use of Courcelle's theorem in this domain is a reasonable contribution. The paper is also careful to state its dependence on the external Zeng--Mehta characterization and on standard complexity results. However, the current version contains a serious gap in the proof of Theorem 4 that affects a central tractability claim, an incomplete proof step in Theorem 12 that affects Theorem 1, and unverified min-uncut counts in the gadgets of Theorem 2. Because these issues are load-bearing for the main claims, the manuscript requires substantive revision before it can be accepted.","major_comments":[{"comment":"The 2-SAT reduction is not sound as written because it discards 0-edges that have both endpoints inside a single root-state neighborhood. In the reduction, for a state u, all G0-edges with an endpoint in N1(u) are reconnected to the opposite new vertex v; an edge with both endpoints in N1(u) therefore becomes a loop. Since G0 is a simple graph and the text does not state that such loops are kept as unit clauses, the most straightforward reading is that they are omitted. This can turn infeasible root states into feasible ones. Concretely, take two P3 components with centers a,d and leaves b,c and e,f, and add the 0-edges bc, ad, ae, bd, cd. By Proposition 8 no rooting works: the four root-pair types are blocked respectively by ad, ae, bd/cd, and bc. In the reduced 2-SAT instance, the clauses for ad, ae, bd, and cd forbid three of the four pairs, but the loop obtained from bc is dropped, so the center/center pair is unconstrained and the 2-SAT instance is satisfiable. The appendix's claim that 'the neighborhoods of the new states are the same' fails for such internal 0-edges. The proof must explicitly encode these loops as unit clauses (or otherwise preserve the infeasibility of states whose neighborhood is not independent), and the correctness argument must account for them. This is a load-bearing error in the proof of Theorem 4.","section":"Section 5.3 and Appendix, 'Missing details of the proof of Theorem 4'"},{"comment":"Step 2 as written is ambiguous about how many value-1 edges a root receives from B. The text says: 'For each vertex u selected as a root in the previous step, check if there is a vertex v in B such that w(uv)=1 and if so, orient the edge uv towards u.' If u has several 1-edges to B, the instruction to 'orient the edge uv towards u' is naturally read as orienting all of them towards u. Then a root u receives multiple 1-items, and a B-vertex that ends up with no 1-item can strongly envy u (conditions (1)--(3) of Observation 6 are all satisfied when u has another item besides the shared edge). The proof rules out strong envy from A to B and from B to B, but it does not rule out strong envy from B to A. The construction should orient at most one incident 1-edge towards each root from Step 1, and orient all other 1-edges between A and B towards their B endpoints; then every vertex in A has exactly one 1-item, so condition (3) of Observation 6 fails for any envier in B. The statement may be true, but the proof as written does not establish an EFX orientation. This gap affects Theorem 1, which relies directly on Theorem 12.","section":"Section 4.1, Theorem 12, Step 2"},{"comment":"The min-uncut number of the three gadgets is asserted but not proved. The text states that the first gadget 'will have min-uncut number two', that the second 'again ... will have min-uncut number two', and that in the third gadget the single m-valued edge is 'the only edge contributing to the min-uncut number'. Since the hardness claims explicitly require min-uncut number exactly 2 in the binary cases and min-uncut number exactly 1 in the almost-binary case, these assertions are load-bearing. The authors should provide the explicit bipartition of the base construction (including a1,a2,b1,b2 and the auxiliary trees) and prove that deleting fewer than the claimed number of edges cannot make the graph bipartite. Without this verification, the hardness results for exactly these min-uncut values are not established.","section":"Section 4.2, Theorem 2"}],"minor_comments":[{"comment":"The name 'Christadolou' in the abstract is a typo; it should be 'Christodoulou'.","section":"Abstract / Introduction"},{"comment":"'ACore of a tree' should be 'A core of a tree', and the sentence following the definition should end with a period.","section":"Definition 20"},{"comment":"The sentence 'We root Tat an arbitrarily chosen non-leaf' is missing a period and a definite article. The dynamic programming table D is defined with modes 'no, bot, top' but the recurrence uses both j and q for children; please make the indexing consistent.","section":"Appendix, Proof of Lemma 25"},{"comment":"The planarity of the final graph after applying Lemma 17 is argued in a single sentence ('embed T such that its leaves are ordered according to P'). Since the theorem asserts planarity as a key restriction, please provide a short formal argument or a figure showing that the replacement preserves the planar embedding.","section":"Appendix, Proof of Theorem 3"},{"comment":"The definition of split orientation is clear, but the phrase 'no two arcs in M can share their heads or tails' is followed by a footnote defining head and tail that is not referenced in the main text at that point; consider moving the definition into the main text or adding a forward reference.","section":"Section 6.3.1"}],"recommendation":"major_revision","confidential_remarks":"The most serious issue is the unsound 2-SAT reduction in the proof of Theorem 4; I recommend asking the authors to provide a complete corrected proof that explicitly handles 0-edges inside a single root-state neighborhood. The issue in Theorem 12 and the missing min-uncut verification in Theorem 2 also need to be addressed. If the authors can fix these points, the paper's contributions are significant and suitable for a journal; in its current form the central tractability claims are not fully substantiated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know before you read it. The paper actually advances the EFX-orientation program: it replaces the Zeng-Mehta bipartite/3-chromatic wall with a real dichotomy around min-uncut (distance 1 tractable, distance 2 hard, one non-binary edge hard at distance 1), and it argues that P5s in the value-1 graph are the essential obstruction, complementing hardness with a P5-free algorithm and a constant-treewidth result. Good, serious work.\n\nThe soft spot is real. The proof of Theorem 4, the P5-free linear-time algorithm, is incomplete as written. The appendix reduces each tree to two states and reconnects 0-edges from the 1-neighborhood of a state to the opposite new vertex. If a 0-edge has both endpoints inside one state's neighborhood, it becomes a loop and is silently dropped because G0 is simple. That drops the constraint that the state is infeasible. I reproduced the two-P3 example from the stress-test note: no rooting exists, but the reduced 2-SAT instance is satisfiable. The fix is cheap—keep those loops as unit clauses—but the appendix's claim that the new states have the same neighborhoods is false for internal 0-edges.\n\nTheorem 12 has a smaller bug: Step 2 orients every 1-edge from a root to B toward the root, so a root can get multiple 1-items, contradicting the proof's 'at most one item' line and breaking EFX. One-line fix: orient at most one such edge toward the root, the rest away. The min-uncut counts for the three gadgets in Theorem 2 are asserted without proof; I suspect they are right but they should be demonstrated.\n\nThe parameterized core/split-orientation material is inventive and largely coherent; the treewidth result is routine Courcelle as the authors concede. The reliance on Zeng-Mehta's characterization is explicit and the one self-citation is a black-box min-uncut routine, not circular.\n\nWho benefits: people working on graphical fair division, distance-from-triviality parameterizations, and the EFX existence question. It deserves a serious referee; the right path is major revision to fix Theorem 4's reduction and clarify Theorem 12. I would cite the min-uncut dichotomy once the small fixes are confirmed; I'd wait on Theorem 4 until the reduction is corrected.","headline":"A genuinely useful complexity map for EFX orientation with one real gap: the Theorem 4 2-SAT reduction drops internal 0-edges and is incomplete as written, but the min-uncut dichotomy and parameterized work are solid and deserve a serious referee.","tokens_in":34603,"tokens_out":7758,"would_cite":true,"duration_ms":74910,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32","68Q25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"EFX-orientation on graphs is linear-time solvable one edge from bipartite, NP-complete two edges away, with P5 paths as the core obstruction.","keywords":["EFX-orientation","fair division","graph orientation","binary additive valuations","min-uncut number","P5-free graphs","treewidth","parameterized complexity"],"falsifier":"Compute, for all preprocessed graphs up to ten vertices whose value-1 subgraph is a $P_5$-free forest, both the existence of an EFX-orientation by brute force over all orientations and the paper's root/independent-set condition; any mismatch, or any min-uncut-1 binary instance with no EFX-orientation, would refute the central claims.","tokens_in":2425,"feed_emoji":"⚖️","tokens_out":2403,"duration_ms":130122,"temperature":0.7,"pith_summary":"This paper pins down the computational boundary of EFX-orientation, the fair-division problem where agents are vertices, items are edges, and each item must go to one of its endpoints so that no agent strongly envies another. With symmetric, additive, and mostly binary valuations, it shows that bipartite graphs are not the only easy case: every instance one edge-removal away from bipartite is solvable in linear time, but two edge-removals make the problem NP-complete, and a single non-binary value already brings NP-hardness at distance one. The same boundary reappears inside the graph: the obstruction is an induced path on five vertices in the subgraph of value-1 edges, and excluding that path restores linear-time solvability. These results give a nearly complete map of which graph structures make fair allocations easy or hard to compute, plus linear-time algorithms on constant-treewidth graphs.","feed_headline":"Fair division on graphs: one edge from bipartite is easy, two is hard","feed_subtitle":"A single removal from bipartite is always fair-orientable; a second removal is NP-hard, and the culprit is a five-vertex path.","key_machinery":"The load-bearing machinery is the rooting characterization: after preprocessing, $G_1$ is a forest of trees, and an EFX-orientation exists exactly when each tree can be rooted so that the union of the roots' 1-neighborhoods is an independent set in $G_0$ (Proposition 8). All algorithms and reductions work on this root-placement problem. To tame it, the paper introduces the core of a tree, a maximal subtree in which no vertex is adjacent to two leaves, and a leaf-merging lemma showing that only non-dominated rootings matter and that each small core has at most two genuinely distinct states. The $P_5$-free case reduces to 2-SAT, the treewidth case is expressed in MSO and solved by Courcelle's theorem, and the hardness reductions encode constraints on roots directly as 0-edges between root-neighborhoods. The min-uncut-1 algorithm instead uses a partition of the vertices into parts whose induced structure guarantees a valid orientation.","core_discovery":"The central claim is a sharp pair of dichotomies. For binary symmetric additive valuations, the min-uncut number, the minimum number of edges whose deletion makes the graph bipartite, is decisive: Theorem 1 gives a linear-time algorithm for every instance with min-uncut number 1, while Theorem 2 proves NP-hardness for min-uncut number 2 and hardness for min-uncut number 1 when one edge has a non-binary value. The paper also identifies the combinatorial reason behind this boundary: induced paths on five vertices, $P_5$, in the subgraph $G_1$ of value-1 edges are the essential obstruction. Theorem 3 shows NP-completeness persists even when every component of $G_1$ is a $P_2$, $P_3$, or $P_5$, $G_0$ has maximum degree 1, and $G$ is planar; Theorem 4 shows linear-time solvability whenever every component of $G_1$ is $P_5$-free or contains a cycle. The paper further proves that constant-treewidth graphs are solvable in linear time via MSO logic, and it calibrates the parameterized complexity: with a tree-core notion, instances with few small cores and few big cores are solvable in $\\tau^k n^{O(b)}$ time, while the number of big cores is $W[1]$-hard, so a $f(k)n^{O(1)}$ algorithm is unlikely under standard assumptions.","pith_inferences":["Beyond the paper, the $P_5$ dichotomy suggests a broader pattern: for binary symmetric additive EFX-orientation, tractability of a hereditary class of $G_1$ may be governed by whether the class contains $P_5$; testing other small forbidden induced trees would directly probe this pattern.","Beyond the paper, the sharp min-uncut threshold of 2 suggests that the right parameter for further algorithms is the pair (distance to bipartite, number of non-binary edges), since Theorem 2 shows either parameter alone is insufficient.","Beyond the paper, the core and split-orientation machinery is defined entirely inside $G_1$, with 0-edges used only to forbid root pairs, so the same structural analysis could transfer to EF1-orientations or to chores with costs if analogous root/independent-set characterizations hold there.","Beyond the paper, the planar NP-hardness at constant degree means geometric restrictions alone will not restore tractability, so bounded-treewidth or bounded-core-count algorithms are the natural route for practical instances, and an implementation of the 2-SAT reduction on $P_5$-free inputs would be a useful benchmark."],"forward_implications":["Every EFX-orientation instance with binary symmetric additive valuations and min-uncut number 1 has a solution, and that solution can be found in linear time, so bipartite graphs are not the only easy case.","At min-uncut number 2 the same valuation class becomes NP-complete, placing the easy-hard boundary exactly at the second deleted edge; allowing even one non-binary edge moves hardness to min-uncut number 1.","If every component of $G_1$ is $P_5$-free, the instance is linear-time solvable; the planar hardness instances with $G_1$ components $P_2$, $P_3$, or $P_5$ show that induced five-vertex paths are the essential obstruction.","On graphs of constant treewidth the problem is linear-time solvable, and because known results make it NP-hard on constant-vertex-cover graphs once valuations are not binary, the binary assumption in this result is necessary.","Parameterized by the number of large cores in $G_1$, the problem is $W[1]$-hard, so the $\\tau^k n^{O(b)}$ running time of the core-based algorithm is essentially the best one can expect under standard parameterized-complexity assumptions."],"supporting_citations":[{"why":"Supplies Proposition 8, the root-independent-set characterization of EFX-orientation that all theorems in this paper reduce to, and the bipartite polynomial-time baseline.","marker":"[Zeng and Mehta, 2024]"},{"why":"Introduced EFX-orientation, proved the general problem NP-complete, and provided the reduction template whose $G_1$ contains $P_2$, $P_3$, and $P_5$ components.","marker":"[Christodoulou et al., 2023a]"},{"why":"Established NP-completeness of Planar Monotone 3-SAT, the source problem for the planar hardness result in Theorem 3.","marker":"[de Berg and Khosravi, 2012]"},{"why":"Provides multicolored independent set as the standard $W[1]$-hard source problem used in the reductions for Theorems 2 and 32.","marker":"[Cygan et al., 2015]"},{"why":"Gives the linear-time test for whether the min-uncut number is at most 1, used to turn the constructive argument into the Theorem 1 algorithm.","marker":"[Iwata et al., 2016, Ramanujan and Saurabh, 2017]"},{"why":"Courcelle's MSO model-checking theorem, the engine behind the constant-treewidth linear-time algorithm in Theorem 5.","marker":"[Courcelle, 1990]"},{"why":"Linear-time evaluation of MSO-definable problems on tree-decomposable graphs, used alongside Courcelle's theorem in Theorem 5.","marker":"[Arnborg et al., 1991]"},{"why":"The linear-time 2-SAT algorithm that decides the two-state root problem in the $P_5$-free case of Theorem 4.","marker":"[Aspvall et al., 1979]"},{"why":"Shows NP-hardness with constant vertex cover when valuations are not binary, establishing that the binary assumption in Theorem 5 is essential.","marker":"[Deligkas et al., 2024]"}],"fun_headline_variants":["EFX orientation: 1 edge from bipartite easy, 2 NP-hard","Fair division on graphs: one step to bipartite easy, two hard","Sharp EFX boundary: min-uncut 1 solvable, 2 hard","Even one non-binary value makes EFX hard one edge from bipartite"],"cache_read_input_tokens":36608,"weakest_assumption_plain":"Everything rests on a previously proved equivalence: a preprocessed graph has a fair orientation exactly when its trees of value-1 edges can each be given a root so that no two root-neighbors are joined by a value-0 edge; if that equivalence is not exact, the algorithms and reductions built on it collapse.","fun_headline_variants_meta":{"raw":{"variants":["EFX orientation: 1 edge from bipartite easy, 2 NP-hard","Fair division on graphs: one step to bipartite easy, two hard","Sharp EFX boundary: min-uncut 1 solvable, 2 hard","Even one non-binary value makes EFX hard one edge from bipartite"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00089,"raw_usage":{"total_tokens":3964,"prompt_tokens":1194,"completion_tokens":2770,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":810,"completion_tokens_details":{"reasoning_tokens":2685}},"tokens_in":810,"tokens_out":2770,"duration_ms":21860,"temperature":1.0,"reasoning_tokens":2685,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:37:55.212233+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, for all preprocessed graphs up to ten vertices whose value-1 subgraph is a $P_5$-free forest, both the existence of an EFX-orientation by brute force over all orientations and the paper's root/independent-set condition; any mismatch, or any min-uncut-1 binary instance with no EFX-orientation, would refute the central claims.","supporting_citations":[],"review_version":2}