| paper | The Parameterized Complexity of Connected Fair Division |
| authors | Argyrios Deligkas, E. Eiben, R. Ganian, Thekla Hamm, S. Ordyniak |
| venue | IJCAI 2021 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, hence \(\mathrm{NP}\)-hard. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 3
statement extracted from the paper’s text layer
Given a finite graph \(G=(V,E)\), one agent type \t\ with \u_t(v)=1\ for every \v\, and rational per-capita supplies \(\rho_v)_{v\in V}\, decide whether there are nonnegative rational masses \lambda_{t,S})\ over connected integral bundles S\subseteq V)\ with finite support such that \sum_S\lambda_{t,S}=1\), \(\sum_{S\ni v}\lambda_{t,S}=\rho_v\)\ for every \v\, and support-wise envy-freeness: \(\lambda_{t,S},\lambda_{t,R}>0\) implies \(u_t(S)\ge u_t(R)\).
A high-multiplicity connected fair-division model with type masses \(\mu_t\), per-capita item supplies \(\rho_v\), and configuration masses \(\lambda_{t,S}\); each individual receives an integral connected bundle, while feasibility under EF or EFX is tested across all supported bundles.
The aggregate λ formulation does not require supported bundles to form one common connected partition, so Proposition 3's exact finite ECP object and its hardness proof are not preserved automatically.
fatal: False
The mirror covers the all-ones EF version of Proposition 3 and the \((\mathrm{vc}(G),|T|,\mathrm{val})\)-parameterized EFX analogue of Theorem 8; it leaves the remaining XP, W[1]-hardness, and fairness-boundary results unexamined.
My lead is a continuous-population version of the paper’s connected fair-division problem, with the graph and bundle integrality preserved.
Take a finite item-location graph \(G=(V,E)\) and a finite set \(T\) of complete agent types. Type \(t\) has additive valuation \(u_t:V\to\mathbb N\), and \(\mu_t\) is its population mass, with \(\sum_t\mu_t=1\). To make an atomless population compatible with indivisible items, let \(\rho_v\in[0,1]\) be the per-capita supply of item-location \(v\). In a finite population of size \(N\), this means \(N\rho_v\) indivisible copies of \(v\), with each agent receiving at most one copy of any location.
A connected bundle is a set \(S\subseteq V\) such that \(G[S]\) is connected. The decision variable is \(\lambda_{t,S}\), the mass of type-\(t\) agents receiving the integral bundle \(S\). It must satisfy
\[ \sum_S\lambda_{t,S}=\mu_t \]
and
\[ \sum_{t,S:v\in S}\lambda_{t,S}=\rho_v \]
for every \(t\) and \(v\). Thus \(\lambda\) is fractional only across agents: every individual represented by positive mass still receives an indivisible, connected bundle.
Fairness is imposed support-wise, not merely on type averages. For example, the allocation is envy-free if, whenever \(\lambda_{t,S}>0\) and \(\lambda_{t',R}>0\),
\[ u_t(S)\ge u_t(R). \]
EF1 and EFX use exactly the paper’s removable-item definition, with
\[ \operatorname{rem}(R)=\{v\in R:G[R\setminus\{v\}]\text{ is connected}\}. \]
Proportionality becomes
\[ u_t(S)\ge \sum_{v\in V}\rho_vu_t(v). \]
The objective is feasibility: output a finite-support rational \(\lambda\), or report that none exists. Clearing denominators gives a two-way dictionary with finite high-multiplicity instances: \(N\mu_t\) agents of type \(t\), \(N\rho_v\) copies at \(v\), and \(N\lambda_{t,S}\) agents receiving \(S\).
This is a plausible regime for many employees, households, or duty-assignees sharing a small number of valuation profiles over a fixed spatial or organizational topology. The number of agents \(N\) is large, while \(|T|\), the number of valuation types, may remain small. The repeated item supply is not an outcome-space relaxation: the graph remains discrete, bundles remain integral, and only the population and the supply rates are continuized.
The strongest anchor is Proposition 3, proved in this paper. It states:
For every \(\phi\in\{\mathrm{PROP},\mathrm{EF},\mathrm{EF1},\mathrm{EFX}\}\), \(\phi\)-CFD is NP-hard even when there are exactly two agents and both agents have the identical all-ones valuation \(u_1=u_2=1\).
The reduction is from EQUITABLE CONNECTED PARTITION. I would mirror its EF case with the following problem.
Mass-Connected EF Feasibility\(_\infty\). Given \(G\), one agent type \(t\) with \(\mu_t=1\) and \(u_t(v)=1\) for every \(v\), and rational supplies \(\rho_v\), determine whether there is a mass distribution over connected integral bundles satisfying the supply equations and support-wise envy-freeness.
The literal normalization of the paper’s two-agent instances is \(\rho_v=\tfrac12\) for every \(v\). In that case every positive-mass bundle must have the same cardinality, and the average bundle size is \(|V|/2\). For a large population, the question becomes whether the graph admits a population distribution over connected half-sized bundles with the required location marginals.
I would expect this to be hard for continuum-specific reasons, rather than claiming that the paper’s ECP reduction transfers unchanged. The mass variable \(\lambda\) can mix many connected partitions, so the original two-bundle integrality argument may disappear. But feasibility now resembles membership in a convex hull of connected-set incidence vectors, and the associated pricing problem can involve selecting a high-weight connected subgraph. That is a genuine computational question created by the continuous population model. The relevant follow-ups are whether the problem is NP-hard already for one type, whether it is tractable on trees or bounded-treewidth graphs, and whether the apparent configuration LP has a polynomial separation oracle.
A useful algorithmic companion is Theorem 8, also proved in this paper. It states:
For every \(\phi\in\{\mathrm{PROP},\mathrm{EF},\mathrm{EF1},\mathrm{EFX}\}\), \(\phi\)-CFD is fixed-parameter tractable when parameterized by the vertex-cover number of \(G\), the number of agent types, and
\[ > \operatorname{val}=\bigl|\{u_i(v):i\in A,\ v\in V\}\bigr|. > \]
The continuous problem I would attach to it is Vertex-Cover–Type–Value Mass-Connected EFX\(_\infty\): the same feasibility problem above, with EFX fairness, parameterized by
\[ \kappa=\operatorname{vc}(G),\qquad \tau=|T|,\qquad q=\bigl|\{u_t(v):t\in T,v\in V\}\bigr|. \]
I expect this version to be FPT. The proof strategy suggested by Theorem 8 survives conceptually: vertices outside a vertex cover can be grouped by their neighborhood in the cover and their valuation vector across the \(\tau\) types. The resulting finitely many item classes can be handled by an integer or configuration formulation whose numerical right-hand sides are the rational masses and supplies. The paper’s theorem does not itself prove this continuous result, but it gives a concrete structural route to it.
The weakest point is the supply scaling. With a strictly finite item set and an atomless population, most agents would receive nothing, so some co-modification is unavoidable. Repeated item-location copies and support-wise fairness are therefore doing real modelling work. A referee who rejects that co-modification would reject the mirror for a technical reason, but under the programme’s stated high-multiplicity principle it is natural: it is the same graph-allocation problem in a regime with many repeated agents and repeated item slots.
I would limit the claimed scope to Proposition 3 and Theorem 8. I would not claim that the paper’s other parameterized boundaries automatically transfer. The central positive case is that these two named results expose a meaningful continuous frontier: Proposition 3 supplies a graph-connectivity hardness question whose discrete reduction may dissolve, while Theorem 8 supplies a plausible FPT boundary in the number of types and structural complexity.
The strongest negative case is that both anchors lose the paper’s population axis in the very restrictions that make them attractive.
Proposition 3 is NP-hard with exactly two agents, identical all-ones valuations, and a unique copy of every item. Its hard object is an integral partition of one finite graph into two connected bundles. That is not a multiplicity phenomenon: the agents are interchangeable, and the difficulty lies in choosing one connected partition of the named vertices.
The proposed mirror exposes this collapse. With one type, \(\mu_1=1\) is fixed, so the society is not actually a variable. Under all-ones valuations and EF, every used bundle must have the same cardinality. With \(\rho_v=\tfrac12\), the problem becomes, essentially,
\[ \left(\tfrac12,\ldots,\tfrac12\right) \in \operatorname{conv} \left\{ \chi^S: G[S]\text{ is connected},\ |S|=|V|/2 \right\}. \]
That is a convex-hull or lottery problem over connected subsets. The original connected partition has disappeared: different bundles in the support need not be complements, or even belong to the same allocation. The continuous variable is therefore doing outcome-space fractionalization, while the population itself has collapsed to one anonymous type.
There is a dichotomy here that survives attempts to improve the formulation. If one requires every replicated copy of the graph to receive a complete connected allocation, then the continuum is a distribution over complete connected partitions. Its support is nonempty exactly when the original finite instance has a solution, so the population limit adds no substantive question. If instead one imposes only aggregate location marginals, as the proponent does, one obtains a different fractional connected-set problem. That may be interesting, but it is not a continuous version of Proposition 3’s computational object.
Replicating items does not remove this problem. Disjoint graph copies yield independent finite allocations; a blow-up with edges between copies changes connectivity; co-located copies require a new convention about whether copies are adjacent. The resulting model can be sensible, but it is a new resource-supply model whose central variable is the configuration distribution \(\lambda\), not the population distribution. Clearing denominators establishes a relation to a newly defined replicated-item problem, not a two-way dictionary with the paper’s CFD instances.
Theorem 8 is a weaker anchor for the same reason. Its FPT result is driven by grouping item vertices outside a vertex cover according to neighbourhoods and valuation vectors, then assigning those classes to named agents. The number of agent types is already a compression device inside the discrete algorithm; the theorem does not identify a population phenomenon that becomes visible only in the limit.
A faithful replication of Theorem 8 merely replaces repeated named agents and repeated item copies by integer counts. That is a high-multiplicity encoding of the same allocation problem. The continuous version with \(\lambda\) is different: EFX must hold for every bundle in the support, and a single type may be split among exponentially many connected configurations. The theorem’s item-class argument does not establish an FPT algorithm for that support-wise configuration problem; one would need a new configuration or separation theorem. Such a theorem could be valuable, but it would be a result about fractional connected-set allocation, not a consequence or mirror of Theorem 8.
The paper does make a high-multiplicity story more plausible than many papers: it explicitly uses agent types, and repeated employees with repeated duties or facility slots are not incoherent. Existing type-based work is supporting evidence, not a novelty collision. So the universal negative is not airtight. Once per-capita item supplies are admitted, a multi-type replicated-resource model is defensible. But these two anchors do not establish it: Proposition 3 has no active population dimension, while Theorem 8 either remains a compressed discrete problem or becomes a new fractional configuration problem. The best negative verdict is therefore that the proposed mirrors are under-anchored and fail the active-population test, not that every conceivable replicated-resource variant is worthless.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.