EF(X) Orientations: A Parameterized Complexity Perspective

Christos Pergaminelis; Edouard Nemery; Manolis Vasilakis; Minas Marios Sotiriou; Sotiris Kanellopoulos

REVIEW 2 major objections 4 minor 1 cited by

EF(X) Orientations: A Parameterized Complexity Perspective

T0 review · 2 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2512.25033 v3 pith:P6WMHT55 submitted 2025-12-31 cs.DS

Sotiris Kanellopoulos , Edouard Nemery , Christos Pergaminelis , Minas Marios Sotiriou , Manolis Vasilakis This is my paper · ORCID

classification cs.DS MSC 05C8568Q2791B32

keywords EForientationEFXfairdivisiongraphparameterizedcomplexitytreewidthvertexcovercharity

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper's central claim is that envy-free (EF) and envy-free-up-to-any-good (EFX) orientations have essentially the same parameterized complexity when edge weights are polynomially bounded: both are W[1]-hard parameterized by vertex cover, XNLP-hard by pathwidth, and XALP-hard by treewidth, with no n^{o(vc/log vc)} algorithm under ETH; and both are solvable in (n+m)^{O(tw)} time by dynamic programming over a tree decomposition, matching the lower bound up to a log factor. As a byproduct, it improves the known NP-hardness constant for EFX orientation to vertex cover 4, and it transfers all EF hardness results to EFX by adding just two vertices. For binary valuations the two problems separate: EF orientations are decidable in linear time, including the minimum-charity variant, while EFX orientations remain NP-hard. The motivation is that these graph-orientation models are a natural fair division setting, and the results effectively close the structural parameterization question for the polynomial-weight regime.

What carries the argument

The central mechanism for the tractability results is the signature DP over a nice tree decomposition: for each bag, the algorithm stores a triple (r, d, k) where r caps each vertex's received value at the maximum shared weight W, d records the value it demands in order not to envy (or, for EFX, not to strongly envy) vertices outside the bag, and k counts the number of unoriented (charity) edges. The closure of these signatures under introduce, forget, and join nodes is what yields the W^{O(tw)} running time and, for polynomially bounded weights, (n+m)^{O(tw)}. For binary EF orientations, the load-bearing structural theorem is the componentwise four-property characterization of the all-1 sub

What would settle it

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<n yet SAT is still hard, the lower-bound proof needs an extra padding step. Alternatively, exhibit a small multigraph with W=3 and treewidth 2 where the treewidth DP's revenue–demand signature set fails to capture the true minimum charity, refuting the algorithm's correctness.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes a nearly complete complexity picture for EF orientations and, by transfer, for EFX orientations. For binary valuations, it characterizes EF existence componentwise via four local properties (a circuit of length at least 3, a 1-0 edge, an even nonzero parallel edge count, or a singleton) and derives a linear-time algorithm for both EF orientation and minimum-charity EF orientation. For arbitrary weights it proves NP-hardness even on 3-regular graphs with weights {1,2} and weak NP-hardness for vertex cover 2; for polynomially bounded weights it proves W[1]-hardness by vertex cover, XNLP-hardness by pathwidth, XALP-hardness by treewidth, and an ETH lower

Load-bearing premise

The SETH lower bound assumes every variable edge in the reduction is heavy (weight at least 2), but the construction sets w_i=1 when a variable appears exactly once positively and once negatively, so the final step only yields a (2−ε)^n SAT algorithm if k is Ω(n), which is not guaranteed without padding.

Editorial extensions

If this is right

EF orientation on binary valuations is solvable in linear time, including the minimum-charity version, so on 0/1-weighted graphs fair allocations can be found quickly as long as each component satisfies one of the four structural properties.
For polynomial weights, both EF and EFX orientation admit (n+m)^{O(tw)} algorithms and no n^{o(vc/log vc)} algorithm under ETH; thus the treewidth parameterization is effectively tight up to a log factor in the exponent.
EFX orientation is weakly NP-complete for graphs of vertex cover number 4 and for multigraphs with 4 vertices, improving the previous constants 8 and 10.
The heavy-edge parameterization has a 2^k n^{O(1)} algorithm, and under SETH this is optimal up to polynomial factors.
The minimum-charity versions inherit the same algorithmic guarantees, so the smallest number of edges to donate to restore EF(X) can be computed within the same running times.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the SETH lower bound survives its current heavy-edge gap, the 2^k algorithm is optimal; a natural next step is to design a similar FPT algorithm for multigraphs, which the paper leaves open.
The treewidth DP scales as W^{O(tw)}, so the polynomial-weight cutoff is what makes it XP; for super-polynomial weights, one would expect NP-hardness even for constant treewidth, a boundary the paper does not probe.
The EF-vs-EFX separation at binary valuations suggests that envy-freeness encodes more combinatorial structure; examining other valuation regimes (e.g., weights bounded by a constant) might reveal further complexity gaps between the two notions.
Because the reductions are simple and the charity algorithms are constructive, the treewidth DP could in principle be adapted to output an actual orientation, a practical point the paper does not emphasize.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the 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.

The 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.

The 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.

Who 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.

Referee Report

2 major / 4 minor

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.

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 (2)

[Section 4.2, Theorem 23 and Corollary 24] 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 3.3, Theorem 9] 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.

minor comments (4)

[Section 3.1] 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.
[Appendix B, proof of Theorem 5] 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.
[Appendix B, Lemma 32] 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.
[References] The reference [Steihaus, 1948] should be 'Steinhaus'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation chain rests on external hardness hypotheses and standard black-box reductions, not on fitted predictions or load-bearing self-citations.

full rationale

The paper's central reductions and algorithms are built from standard external results used as black boxes: SETH and ETH, 2P2N-3SAT, PARTITION, TARGETOUTDEGREEORIENTATION, and UPPER DEGREE-CONSTRAINED GRAPH ORIENTATION. No parameter is fitted to a subset of data and then relabeled as a prediction, and no claimed theorem is shown to be equivalent to its own input by construction. The EF treewidth DP (Theorem 14) is an explicit constructive algorithm with bounded state; the EFX DP (Theorem 23) is explicitly deferred to a revised version, which is a proof-completeness concern, not circularity. The SETH reduction in Theorem 9 has a possible gap concerning variables appearing once positively and once negatively, but that is a correctness/parameter-analysis issue rather than a circular reduction. Self-citations in the bibliography are background citations and are not load-bearing for the paper's main derivations. Therefore the paper does not exhibit a circular derivation chain.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The paper is a complexity-theoretic work; it introduces no fitted constants and no invented entities. Its results are conditional on standard conjectures (SETH, ETH) and on the correctness of black-box results from prior literature (hardness of TARGETOUTDEGREEORIENTATION, NP-completeness of 2P2N-3SAT, polynomial solvability of UDCGO). These are standard practice, not circularity.

assumptions (7)

domain assumption SETH and ETH are true
Used for conditional lower bounds in Theorems 9, 12, and 13; no proof, standard conjectures in fine-grained complexity.
domain assumption TARGETOUTDEGREEORIENTATION is W[1]-hard by vertex cover, XNLP-hard by pathwidth, XALP-hard by treewidth with unary weights
Black-box hardness results relied upon in Theorem 12, from Bodlaender et al. 2022 and Bodlaender & Szilágyi 2024.
domain assumption 2P2N-3SAT is NP-complete
Used in Theorem 10 for 3-regular hardness, citing Berman et al. 2003 and Darmann & Döcker 2021.
domain assumption UPPER DEGREE-CONSTRAINED GRAPH ORIENTATION has a polynomial-time algorithm
Used in Theorem 13 to decide extendability after fixing heavy-edge orientations; cited to Frank & Gyárfás 1978.
standard math Tree decompositions and nice tree decompositions can be constructed; standard DP over nice tree decompositions is valid
Used in Theorems 14 and 23; background in Appendix A.
standard math Preprocessing Observation 3: edges with zero value for both endpoints can be removed, and zero-one edges can be oriented towards the positive endpoint without affecting EF existence
Stated and argued in Section 3; used throughout the paper.
standard math Observation 4 / Theorem 4: a vertex that has received an edge of weight 1 can be used to orient unoriented unit-weight edges while preserving envy-freeness
Key lemma in the structural characterization; proof given in Section 3.1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of EF(X) Orientations: A Parameterized Complexity Perspective." pith.science (2026). https://pith.science/paper/P6WMHT55

@misc{pith2026251225033,
  author       = {Pith},
  title        = {Pith review of: EF(X) Orientations: A Parameterized Complexity Perspective},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P6WMHT55}},
  note         = {Machine review of arXiv:2512.25033}
}

read the original abstract

The concept of fair orientations in graphs was introduced by Christodoulou, Fiat, Koutsoupias, and Sgouritsa in 2023, naturally modeling fair division scenarios in which resources are only contested by neighbors. In this model, vertices represent agents and undirected edges represent goods; edges have to be oriented towards one of their endpoints, i.e., allocated to one of their adjacent agents. Although EFX orientations (envy-free up to any good) have been extensively studied in this setting, EF orientations (envy-free) remain unexplored. In this work, we initiate their study, mostly under the lens of parameterized complexity, presenting various tractable cases, hardness results, and parameterizations. Our results concern both simple graphs and multigraphs. Interestingly, many of our results transfer to EFX orientations, thus complementing and improving upon previous work; notably, we answer an open question regarding the structural parameterized complexity of the latter problem on graphs of polynomially-bounded valuations. We also show that EF orientations are tractable in cases in which EFX orientations are not, particularly for binary valuations. Lastly, we consider charity in the orientation setting, establishing algorithms for finding the minimum amount of edges that have to be removed from a graph in order for EF(X) orientations to exist.

Figures

Figures reproduced from arXiv: 2512.25033 by the authors.

**Figure 1.** An example of a connected component C of G ′ that satisfies Property 2 of Theorem 5, i.e., some vertex receives an edge of weight 1 for itself and weight 0 for the other endpoint. This allows us to repeatedly apply Theorem 4 starting from that vertex, orienting all edges of C to obtain an EF orientation as demonstrated. Using Theorem 5, we can obtain the following. Theorem 6 (⋆). There is an algorithm running in ti… view at source ↗

**Figure 2.** An example of a circuit consisting of 3 vertices, without containing a cycle of length greater than 2. Observe that no vertex is envious of another if the edges are oriented along a cyclic route as shown (assuming all edges have weight 1 for both endpoints). Theorem 7 (⋆). There is an algorithm running in time O(n+m) for MIN-CHARITY EF ORIENTATION with binary valuations. Remark 8. The algorithms of Theorems 6 and 7 … view at source ↗

**Figure 3.** A sketch of our reduction from SAT to EF O [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Figures from the paper (5 more)

**Figure 4.** Figure 4: Our reduction from EF ORIENTATION to EFX ORIENTATION in Theorem 19. If e ∗ is oriented towards d1, then all other edges incident to d1 must be oriented away from d1 to obtain an EFX orientation. Every v ∈ G receives an edge of weight 0, which forces equivalence betwee…

**Figure 5.** Figure 5: An example of a circuit consisting of 3 vertices, without containing a cycle of length greater than 2. Observe that no vertex is envious of another if the edges are oriented along a cyclic route as shown (assuming all edges have weight 1 for both endpoints). edge e /∈ …

**Figure 6.** Figure 6: An example of a connected component C of G ′ that satisfies Property 2 of Theorem 5, i.e., some vertex receives an edge of weight 1 for itself and weight 0 for the other endpoint. This allows us to repeatedly apply Theorem 4 starting from that vertex, orienting all edg…

**Figure 7.** Figure 7: An example of our contstruction in Theorem 9. For simplicity, we only show the part of the graph corresponding to [PITH_FULL_IMAGE:figures/full_fig_p014_7.png]

**Figure 8.** Figure 8: Our reduction from EF O [PITH_FULL_IMAGE:figures/full_fig_p022_8.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

EFX Allocation In (Multi)Hypergraphs
cs.GT 2026-08 conditional novelty 7.0 of 10

Any hypergraph with girth at least 4 admits an EFX allocation under general monotone valuations, and a restricted class of multi-hypergraphs admits one in pseudo-polynomial time.

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.