Source-linked AI summary
A Polynomial Time Characterization For Strongly EFX Orientable Graphs
Jinghan A Zeng
TL;DR
Which graphs guarantee an EFX orientation for every edge valuation remained an open question, while deciding whether an orientation exists is NP-hard. This paper gives a polynomial-time characterization: a connected graph qualifies if it is bipartite or satisfies a specified condition on its nonbipartite block.
Problem
Which graphs always admit an EFX orientation for any edge valuation remained open, even though deciding whether one exists is NP-hard.
Source: §1 · p. 2Method
The paper characterizes strongly EFX-orientable connected graphs using bipartiteness and the block structure and vertex degrees of nonbipartite graphs.
Source: §1 · p. 2Results
A connected graph is strongly EFX-orientable if it is bipartite or has exactly one nonbipartite block B with a degree-2 vertex v in B such that G-v is bipartite.
Source: §1 · p. 2Takeaways & Limitations
The characterization makes it possible to decide in polynomial time whether a graph is strongly EFX-orientable.
Source: §1 · p. 2
Abstract
from arXiv · showhide
Discrete fair division is the problem of dividing a discrete set of goods among agents in a fair manner. In this setting, one of the most sought-after notions of fairness is envy-freeness up to any good (EFX). In 2023, Christodoulou, Fiat, Koutsoupias, and Sgouritsa introduced the idea of a graphical valuation, where the fair division problem is represented by a simple graph where vertices are the agents and the edges are the goods, and each vertex only values incident edges. They showed that an EFX allocation always exists, while determining the existence of an EFX orientation is NP-hard. They posed a open question of determining which graphs always admit an EFX orientation regardless of valuation. These graphs, called strongly EFX orientable graphs, were first studied by Zeng and Mehta in 2025, who demonstrated that all such graphs have chromatic number at most 3, and bipartite graphs always admit an EFX orientation regardless of valuation. In this manuscript, we finish resolving this question by giving a polynomial time characterization of strongly EFX orientable graphs. In particular, we show that a connected graph $G$ is strongly EFX orientable if and only if either of the following is true: (1) $G$ is bipartite, or (2) the block decomposition of $G$ contains exactly one nonbipartite block $B$, and there exists a vertex $v \in B$ such that the degree of $v$ within $B$ is 2 and $G-v$ is bipartite. This proof was discovered by AI, with human intervention to break the problem into the appropriate subproblems.
1 Introduction
The paper characterizes connected graphs that guarantee EFX orientations for every valuation, yielding a polynomial-time decision procedure. Besides bipartite graphs, the characterization includes graphs with exactly one nonbipartite block containing a degree-2 vertex whose deletion makes the graph bipartite.
1 Introduction
- An EFX allocation gives each agent a bundle valued at least as highly as every strict subset of another agent’s bundle, but EFX need not always exist for monotone valuations.Monotonicity means that adding goods cannot decrease an agent’s valuation.Source: §1 · pp. 1–2
- The open question was which graphs admit an EFX orientation for every edge valuation, although deciding whether an orientation exists is NP-hard.In graphical valuations, agents are vertices, goods are edges, and each agent values only incident edges.Source: §1 · p. 2
- Earlier work established that bipartite graphs are strongly EFX-orientable and that all strongly EFX-orientable graphs have chromatic number at most 3 [ZM25].The manuscript presents its characterization as resolving the resulting open question.Source: §1 · p. 2
- Besides bipartite graphs, the characterization includes graphs with exactly one nonbipartite block B and a degree-2 vertex v in B such that G-v is bipartite.The paper states that this characterization makes strong EFX orientability decidable in polynomial time.Source: §1 · p. 2
2 Preliminaries
The preliminaries define fair-division valuations, graphical EFX orientations, and graph connectivity notions, then review examples and prior results relevant to strong EFX orientability.
2.1 Fair Division Definitions
- A graphical valuation lets each agent value only incident edges, and a graph is strongly EFX-orientable if every monotone graphical valuation admits an EFX orientation.Additive valuations assign a bundle the sum of its individual-item values.Source: §2.1 · p. 2
2.2 Connectivity Definitions
- A block is a maximal weakly 2-connected subgraph; cut vertices belong to multiple blocks, which form a tree-like block-cut structure.The section also defines k-connectivity through vertex deletion and internally disjoint paths.Source: §2.2 · p. 3
2.3 Preliminary Examples
- Bipartite graphs are strongly EFX-orientable; one proof orients each partite-set vertex’s favorite edge toward it, then directs remaining edges toward the other part.The proof argues that any remaining envy is from the other part toward vertices receiving at most one edge, making the orientation EFX.Source: §2.3 · pp. 3–4
- A weighted K4 example has no EFX orientation because an edge between two envied vertices prevents either orientation from satisfying EFX.The example uses additive valuations, with edges valued either 1 by both endpoints or 0 by both.Source: §2.3 · p. 4
- Strong EFX orientability is inherited by subgraphs: an orientation for the larger graph restricts to an EFX orientation after outside edges are removed.The proof copies the subgraph valuation and makes edges outside it worthless to both endpoints.Source: §2.3 · p. 4
2.4 Related Work
- Prior work established NP-hardness for deciding EFX-orientation existence in several settings, including simple graphs and restricted graph classes.The cited work also studies EFX allocations on multigraphs and simple hypergraphs.Source: §2.4 · pp. 4–5
3 Characterization of Strongly EFX Orientable Graphs
This section characterizes strongly EFX-orientable connected graphs as bipartite graphs or graphs with a unique nonbipartite block containing a degree-2 vertex whose deletion makes the graph bipartite. It also presents a polynomial-time procedure for deciding strong EFX orientability.
Characterization
- A connected graph is strongly EFX orientable exactly when it is bipartite or has one nonbipartite block containing a degree-2 vertex whose deletion makes the graph bipartite.The degree is measured within that block.Source: §3 · p. 5
3-connected graphs
- A 3-connected graph is strongly EFX orientable if and only if it is bipartite.Tutte’s cycle-space theorem yields an induced non-separating odd cycle in any nonbipartite 3-connected graph; the proof then invokes forbidden odd-cycle configurations.Source: §3 · pp. 5–6
2-connected graphs
- Astra conjectured that a 2-connected nonbipartite graph is strongly EFX orientable exactly when it has a degree-2 vertex whose deletion makes it bipartite.The proof strategy splits graphs lacking such a vertex into cases according to whether their odd cycle transversal is at least 2 or equals 1.Source: §3 · p. 6
Forbidden substructures
- Star-forest obstructions certify failure of EFX orientability, and double-subdividing any edge preserves the existence of such an obstruction.The obstruction is a star forest for which no choice of one witness vertex per tree has an independent set of forest-neighbors.Source: §3 · pp. 7–8
- Four internally vertex-disjoint paths between two vertices, two of odd length and two of even length, forbid strong EFX orientability.The proof constructs a star-forest obstruction for this configuration and uses double subdivision to extend the forbidden family.Source: §3 · pp. 8–9
- A repeatedly subdivided K4 is not strongly EFX orientable when all four original triangles become odd cycles.The proof handles four parity cases by constructing star-forest obstructions and applying double subdivision.Source: §3 · pp. 9–10
2-connected graphs
- For a separating pair in the minimal 2-connected nonbipartite graph considered, every valid partition has a nonbipartite side A and a path side B.The proof rules out both sides being bipartite or both nonbipartite using odd-cycle obstructions, then replaces B with a path while preserving the relevant conditions.Source: §3 · pp. 10–11
- Repeatedly splitting off degree-2 vertices of the minimal graph H yields a graph K with no degree-2 vertices, and K is simple and 3-connected.Each shortcut edge is weighted by the length of its corresponding path in H.Source: §3 · p. 11
Transversal number
- Every 2-connected strongly EFX-orientable graph has τ(G)≤1, yielding a 3-coloring of each 2-connected block and hence of G.The proof excludes τ(G)≥2 by constructing a K4 subdivision whose triangle cycles lift to odd cycles.Source: §3 · p. 12
2-connected graphs
- For nonbipartite 2-connected G, strong EFX orientability is equivalent to having a degree-2 vertex v such that G−v is bipartite.Sufficiency follows because both edges incident to v lie on every odd cycle, so deleting either edge makes G bipartite.Source: §3 · p. 13
Necessity proof
- For 2-connected H with τ(H)=1 and every vertex in T(H) of degree at least 3, deleting v∈T(H) gives bipartite H−v; splitting v yields H′ whose blocks form a path.Source: §3 · p. 13
Block decomposition
- A connected graph is strongly EFX-orientable exactly when it is bipartite or has exactly one nonbipartite block B containing a vertex v of degree 2 with B−v bipartite.The unique-block condition is necessary for a nonbipartite strongly EFX-orientable graph and sufficient even when the graph has cut vertices.Source: §3 · p. 15
Algorithm
- Strong EFX orientability of a connected graph can be decided in O(n(n + m)) time.The algorithm computes the block decomposition, tests blocks for bipartiteness, and checks whether deleting a degree-2 vertex from the unique nonbipartite block makes it bipartite.Source: §3 · p. 16