Tractable Graph Structures in EFX Orientation (d4-conf-sagt-2025-0017)

Given a finite typed graph template \(H=(V,E)\) with rational type masses, binary symmetric additive edge values, every \(G_1\)-component equal to \(P_2\), \(P_3\), or \(P_5\), \(G_0\) of maximum degree \(1\), and a nonatomic copy space \(U\), form \(U\times H\), with agents \((u,v)\) and an indivisible good \((u,e)\) joining the corresponding endpoints. Decide whether there is a measurable integral orientation such that, for almost every \(u\), the orientation in that fiber is EFX.

Input: a finite simple planar graph \(H=(V,E)\), with \(m=|E|\), and symmetric additive edge values \(w:E\to\{0,1\}\). Put \(G_c=(V,\{e\in E:w(e)=c\})\); every component of \(G_1\) is \(P_2\), \(P_3\), or \(P_5\), and \(G_0\) has maximum degree \(1\), where \(P_k\) is the path on \(k\) vertices.
A society is given by its support: the list of the \(\tau=|V|\) types with positive masses \(a_v\), each a binary rational, with \(\sum_v a_v=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Fix \(U=[0,1]\) with Lebesgue measure \(\lambda\). Agents are \(U\times V\), with society measure \(\nu(A\times\{v\})=a_v\lambda(A)\). For each \(u\in U\) and \(e=xy\in E\), there is one indivisible good \((u,e)\), valued at \(w(e)\) by \((u,x)\) and \((u,y)\), and at zero by every other agent.
An integral orientation assigns every \((u,e)\) to exactly one of its two endpoints; for each \(e\), the set of \(u\) selecting either endpoint must be measurable. In each fiber, EFX means envy-freeness after removal of every good from the compared bundle, including goods valued at zero by the comparing agent.

Is deciding whether such a measurable integral orientation is EFX within the fiber for \(\lambda\)-almost every \(u\) in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

Discrete EFX-orientation is \(\mathrm{NP}\)-complete under exactly these graph and valuation restrictions ([source](https://arxiv.org/html/2506.15379v1)). No result settling this exact nonatomic, fiberwise formulation was located in the literature search.

Result. The decision problem is \(\mathrm{NP}\)-complete. Measurable integral orientations that are EFX within almost every fiber exist exactly when the underlying discrete instance admits an EFX orientation.

1. Equivalence with discrete feasibility. For each vertex \(x\), define its value for an edge by \(q_x(e)=w(e)\) when \(e\) is incident to \(x\), and \(q_x(e)=0\) otherwise. Extend this additively to edge bundles.

Let \(\Omega\) be the finite set of orientations of \(H\). For \(\sigma\in\Omega\), write \(B_x^\sigma\) for the edges assigned to \(x\). Define \(F\subseteq\Omega\) to consist of the orientations satisfying
\(\displaystyle q_x(B_x^\sigma)\geq q_x(B_y^\sigma\setminus\{g\})\)
for every pair of distinct vertices \(x,y\) and every \(g\in B_y^\sigma\). The quantification includes goods valued at zero by \(x\), exactly as required.

Consider any measurable integral orientation of the continuum instance. For each edge \(e\) and endpoint \(x\), let \(A_{e,x}\subseteq U\) be the measurable set of fiber coordinates at which \(e\) is assigned to \(x\). For each \(\sigma\in\Omega\), define
\(\displaystyle C_\sigma=\bigcap_{e\in E}A_{e,\sigma(e)}\),
where \(\sigma(e)\) denotes the endpoint receiving \(e\). Each \(C_\sigma\) is measurable because the intersection is finite. These sets partition \(U\).

For every \(u\in C_\sigma\), the identification \((u,e)\mapsto e\) identifies the fiber allocation and all its valuations with the discrete orientation \(\sigma\). Consequently, the set of EFX fibers is precisely
\(\displaystyle S=\bigcup_{\sigma\in F}C_\sigma\).

If the continuum orientation is EFX almost everywhere, then \(\lambda(S)=1\). Thus \(S\) is nonempty, which implies \(F\neq\varnothing\).

Conversely, if \(\sigma\in F\), assign every \((u,e)\) to \((u,\sigma(e))\), for every \(u\in U\). For each edge, its endpoint-selection sets are \(U\) and \(\varnothing\), hence measurable. Every fiber is EFX.

This proves the equivalence. It holds for every allowed mass vector: the masses do not occur in the stipulated fiberwise EFX inequalities.

2. Polynomial reduction establishing hardness. Theorem 3 of Blažej, Gupta, Ramanujan, and Strulo states that discrete EFX-orientation is \(\mathrm{NP}\)-complete for simple planar graphs with symmetric additive binary edge values, every component of \(G_1\) belonging to \(\{P_2,P_3,P_5\}\), and \(G_0\) having maximum degree at most \(1\). Their definition of EFX quantifies over every good in the compared bundle, matching the definition above. [Source: Theorem 3 and Section 2](https://arxiv.org/html/2506.15379v1).

Given an instance of that restricted discrete problem, retain its graph, vertex types, and edge values. Put \(n=|V|\) and \(k=\lceil\log_2 n\rceil\). Enumerate the vertices and assign masses
\(a_i=2^{-k}\) for \(1\leq i<n\), and
\(a_n=1-(n-1)2^{-k}\).

Because \(n\leq 2^k\), the final mass satisfies
\(a_n=(2^k-n+1)/2^k>0\). All other masses are positive, and their sum is \(1\). They are dyadic rationals with \(O(\log(n+1))\) bits per mass, so the complete mass list has polynomial encoding length. The support size is exactly \(\tau=n\).

The graph and valuations remain unchanged, so every required structural restriction is preserved. By the equivalence proved above, the constructed continuum instance is a yes-instance exactly when the discrete instance is a yes-instance. This is a polynomial-time many-one reduction, proving \(\mathrm{NP}\)-hardness.

3. Polynomial verification establishing membership. A certificate consists of one endpoint choice for every edge, using \(m\) bits. Its discrete EFX property can be checked particularly simply.

For a fixed orientation, let \(d_1(x)\) count the value-\(1\) edges assigned to \(x\), and let \(d(y)\) count all edges assigned to \(y\), including value-\(0\) edges. The orientation is EFX if and only if every value-\(1\) edge assigned from \(x\) to \(y\) satisfies
\(d_1(x)\geq 1\) or \(d(y)=1\).

To prove necessity, suppose such an edge \(xy\) has \(d_1(x)=0\) and \(d(y)\geq 2\). Choose another edge \(g\) in \(y\)'s bundle. After removing \(g\), that bundle still contains \(xy\), which \(x\) values at \(1\); meanwhile \(x\)'s own bundle has value \(0\). EFX fails.

For sufficiency, suppose EFX fails for some \(x,y,g\). Since the graph is simple, \(y\)'s bundle contains at most one edge incident to \(x\), namely \(xy\). Thus its value to \(x\), even before removal, is at most \(1\). A strict EFX violation therefore requires \(d_1(x)=0\), a value-\(1\) edge \(xy\) assigned to \(y\), and \(g\neq xy\). Hence \(d(y)\geq 2\), contradicting the stated condition.

Computing these counts and checking the condition takes \(O(m+\tau)\) time. By Section 1, a successful certificate also certifies the continuum instance through its constant measurable realization, and every feasible continuum instance has such a certificate. Therefore the problem belongs to \(\mathrm{NP}\), completing the proof of \(\mathrm{NP}\)-completeness.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is correct: the stated nonatomic, fiberwise decision problem is \(\mathrm{NP}\)-complete. The equivalence, reduction, and certificate verification are rigorous. No major or minor issues were found.

1. Discrete feasibility and measurable fiberwise feasibility

The definition of \(F\) matches the task exactly. It compares every ordered pair of distinct vertices and quantifies over every good in the compared bundle, including goods valued at zero by the comparing agent. Empty compared bundles impose no inequalities, as required.

For each discrete orientation \(\sigma\), the set \(C_\sigma\) is measurable: it is a finite intersection of measurable endpoint-selection sets. Because every good is assigned to exactly one endpoint at every coordinate, the sets \(C_\sigma\) are pairwise disjoint and cover \(U\). Thus the claimed partition is justified.

At each \(u\in C_\sigma\), the fiber contains exactly the goods corresponding to the discrete edges, allocated according to \(\sigma\). The identification preserves both bundles and valuations. Therefore the EFX-fiber set is exactly the finite measurable union
\[ S=\bigcup_{\sigma\in F}C_\sigma. \]

If the orientation is EFX almost everywhere, then \(\lambda(S)=1\). Consequently \(S\) is nonempty, so \(F\) is nonempty. This inference requires neither a measurable selection theorem nor any assumption about the measure of an individual fiber.

Conversely, repeating a discrete EFX orientation at every coordinate produces measurable endpoint-selection sets and satisfies EFX in every fiber. This establishes both directions of the equivalence.

The masses are correctly irrelevant: the task imposes inequalities within each fiber and measures exceptional coordinates using \(\lambda\). It does not impose mass-weighted utility or allocation constraints.

2. Cited hardness theorem and hypothesis matching

The cited source confirms the theorem as stated: Theorem 3 gives \(\mathrm{NP}\)-completeness for binary, symmetric, additive valuations, planar graphs, the specified components of \(G_1\), and maximum degree one in \(G_0\). Section 2 explicitly uses simple undirected graphs and defines strong envy by the existence of any removed good, without a positive-value restriction. Thus the cited result applies to precisely the discrete problem used in the reduction. [Theorem 3 and Section 2](https://arxiv.org/html/2506.15379v1)

The reduction retains the graph and edge values, so all structural hypotheses remain satisfied.

3. Mass construction and encoding

For a nonempty source instance, \(k=\lceil\log_2 n\rceil\) satisfies \(n\leq 2^k\). Hence
\[ a_n=\frac{2^k-n+1}{2^k}>0. \]
All earlier masses are positive, and direct summation gives
\[ \sum_{i=1}^{n}a_i=(n-1)2^{-k}+1-(n-1)2^{-k}=1. \]

The numerators and denominators have \(O(\log(n+1))\) bits, so the complete mass list has polynomial length and can be constructed in polynomial time. Every vertex has positive mass, giving support size exactly \(n\).

The construction also makes sense for \(n=1\): then \(k=0\) and the sole mass is \(1\). An empty graph cannot constitute a valid target society because its mass sum would be zero; this does not affect the reduction from the nonempty hard instances.

The established equivalence proves preservation of yes- and no-instances. The hardness reduction is valid.

4. Certificate characterization and verification

The necessity argument is correct. If a value-one edge \(xy\) is assigned to \(y\), \(x\) receives no value-one edge, and \(y\) receives another edge \(g\), removing \(g\) leaves value at least one for \(x\) in \(y\)’s bundle while \(x\)’s own value is zero.

The sufficiency argument also holds. Since the graph is simple and bundles contain only edges assigned to their endpoints, \(y\)’s bundle contains at most one edge incident to \(x\). Its value to \(x\) is therefore at most one. A strict violation forces \(x\)’s own value to be zero and requires a value-one edge \(xy\) to remain after removal. Thus \(xy\) is assigned to \(y\), the removed edge differs from \(xy\), and \(d(y)\geq2\). This contradicts the stated condition.

Counting assigned edges and checking each value-one edge takes \(O(m+\tau)\) elementary operations; all counters have polynomial bit length. The certificate has \(m\) bits. The equivalence guarantees that such a certificate exists for every feasible continuum instance, and its constant realization certifies continuum feasibility.

Thus membership in \(\mathrm{NP}\) and \(\mathrm{NP}\)-hardness are both established. No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩