| paper | A Little Charity Guarantees Fair Connected Graph Partitioning |
| authors | Ioannis Caragiannis, Evi Micha, Nisarg Shah |
| venue | AAAI 2022 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 13
statement extracted from the paper’s text layer
Given a connected graph \(G=(V,E)\), \(n\ge2\), and a rational population distribution \(\mu\in\mathbb{Q}_{>0}^{V}\) with \(\sum_{v\in V}\mu_v=1\), does there exist a connected pseudo \(n\)-partition \((V_1,\ldots,V_n,R)\) with \(|R|\le n-1\) and \(\max_i\sum_{v\in V_i}\mu_v\le\min_i\sum_{v\in V_i}\mu_v\)?
Site types \(t_v\) are graph vertices, with population mass \(\mu_v\). The decision variables are the indivisible vertex parts \(V_1,\ldots,V_n\) and charity set \(R\); the objective is exact equality of district masses, or minimization of \(\max_i M_\mu(V_i)/\min_i M_\mu(V_i)\), where \(M_\mu(V_i)=\sum_{v\in V_i}\mu_v\).
Residents at a site are forced to move with its indivisible vertex, so the continuous mass affects only the fairness objective and may be viewed as weighted graph partitioning rather than a high-multiplicity version of the paper's original input.
fatal: False
The mirror covers the hardness results in Theorems 13 and 14, with charity and without charity respectively. It does not directly cover the paper's existence lower bounds, polynomial algorithms, conjecture, or charity-approximation tradeoff, although those could motivate further weighted variants.
The strongest honest case is a population-weighted version of the paper’s connected graph partition problem, with Theorem 13 as the lead anchor.
The scenario is connected redistricting or regional service allocation. The graph vertices are precincts, neighbourhoods, offices, or service sites. Each site \(v\) contains a large cohort of otherwise indistinguishable residents. Let \(T=\{t_v:v\in V\}\), where \(t_v\) records the site and every attribute relevant to the partitioning problem. The society is a rational distribution \(\mu\), with \(\mu_v\) the fraction of the total population at site \(v\). A typical regime has \(n\ll |V|=\tau\ll N\): there are \(N\) residents, many repeated at each of \(\tau\) sites, while only \(n\) connected districts or service regions must be formed.
This is not a fractional relaxation of the graph. A site remains indivisible and must be assigned wholly to one district or to charity. What becomes continuous is the population carried by each site. This is exactly the kind of population continuization the programme permits: the society is represented by mass, while the infrastructure and decision constraints remain discrete. It is also recognisable from the paper’s own redistricting motivation and its discussion of weighted nodes.
My lead problem is Charity-Balanced Connected Partition\(_\infty\). An instance consists of a connected graph \(G=(V,E)\), an integer \(n\ge 2\), and a rational distribution \(\mu\in\mathbb{Q}_{>0}^{V}\) with \(\sum_{v\in V}\mu_v=1\). A solution is a pseudo \(n\)-partition \((V_1,\ldots,V_n,R)\) such that \(|R|\le n-1\), the \(V_i\) are pairwise disjoint and cover \(V\setminus R\), and every \(V_i\) is connected via some subset \(R_i\subseteq R\), exactly as in the paper. Its load is \(M_\mu(V_i)=\sum_{v\in V_i}\mu_v\). The question is whether there exists a solution satisfying \(\max_i M_\mu(V_i)\le \min_i M_\mu(V_i)\); equivalently, whether the non-charity population can be divided into \(n\) connected districts of exactly equal mass. The optimization form minimizes \(\max_i M_\mu(V_i)/\min_i M_\mu(V_i)\).
This directly mirrors Theorem 13, which states that checking whether a balanced connected pseudo \(n\)-partition with at most \(n-1\) exclusions exists is NP-complete. Theorem 13 is proved in this paper, not cited from elsewhere. The continuous problem is already NP-hard on the uniform subfamily \(\mu_v=1/|V|\): then \(M_\mu(V_i)=|V_i|/|V|\), so a continuous solution exists exactly when the original balanced pseudo-partition exists. Membership in NP remains straightforward for rational \(\mu\), since a proposed partition can be checked and its masses compared in polynomial time. Thus this mirror is expected to be Class B: the discrete hardness transfers because the reduction’s combinatorics live in the graph topology and the connected partition, not in the number of individually named residents.
The paper’s charity interpretation also survives. An excluded vertex can represent shared public land, a common facility, or a precinct not assigned to any private district. The continuous extension asks a new and natural question: does the optimal amount of charity depend on population mass rather than merely on the number of excluded sites? The current anchor deliberately preserves the paper’s \(|R|\le n-1\) rule, while weighted-charity variants are further questions.
The second mirror is No-Charity \(\alpha\)-Balanced Connected Partition\(_\infty\). Its instance is \(G=(V,E)\), \(n\), a rational positive population distribution \(\mu\), and a fixed \(1\le\alpha<2\). A solution is a partition \((V_1,\ldots,V_n)\) of \(V\) into connected subgraphs. The question is whether \(\max_i M_\mu(V_i)\le\alpha\min_i M_\mu(V_i)\).
This mirrors Theorem 14, also proved in the paper, which states that for any \(\alpha<2\), checking whether an \(\alpha\)-balanced connected \(n\)-partition with no exclusions exists is NP-complete. Again, the uniform distribution gives an exact embedding of the paper’s problem, since the weighted ratio becomes \(\max_i|V_i|/\min_i|V_i|\). The expected classification is therefore also Class B. The nonuniform version is not merely cosmetic: in a real districting instance, population masses are the quantities that matter, and the graph vertices may be precincts with very different populations.
These mirrors cover the paper’s computational hardness results, not its entire algorithmic catalogue. Theorem 1 provides useful fidelity evidence: the paper’s star-like obstruction becomes a population obstruction when each path carries equal or nearly equal mass. Theorem 7’s polynomial construction could also be studied in the weighted model, but I would not claim that theorem as a third anchor without proving that its edge-partition argument survives arbitrary rational vertex masses.
The main further questions are whether the hardness remains under restricted mass patterns, whether weighted instances admit an improved threshold below \(2\), and how the problems behave when parameterized by \(n\), treewidth, the number of distinct mass values, or the number of site types. One can also ask for approximation algorithms and for a continuous-to-finite dictionary: a rational mass vector \(\mu_v=N_v/N\) corresponds to \(N_v\) repeated residents at site \(v\), while finite resident populations converge to the mass model as multiplicities grow.
The weakest point is that this mirror continuizes the residents but leaves the graph sites indivisible. Since \(\tau=|V|\), it compresses the population multiplicity \(N\) without necessarily compressing the graph itself. A referee who expects the agents, rather than the infrastructure, to be the objects being partitioned might call this weighted graph partitioning instead of a genuine continuization. I think that objection is limited: the paper itself motivates connected precinct partitioning by population, and ChoCo’s scope specifically permits a continuous society over discrete structural types. The resulting questions are faithful, precise, and deliberately reveal a Class B boundary where population continuization does not dissolve the underlying graph hardness.
The strongest case against both anchors is that they do not actually continuize the paper’s population, because the paper has no population of allocatable agents. Its objects are graph nodes, and its \(n\) agents are merely the recipients of node bundles. Introducing \(N_v\) residents at vertex \(v\) adds an external layer that never affects feasibility: every resident at \(v\) is forced to travel with the same indivisible vertex. The resulting input \((G,n,\mu)\) is therefore simply a vertex-weighted connected-partition instance.
This is especially clear for Theorem 13. The proposed Charity-Balanced Connected Partition\(_\infty\) has no mass transfer, campaigning, or agent-level choice. The vector \(\mu\) is only a numerical weight in the objective, while all combinatorial content remains in the atomic partition of \(V\). The rational reconstruction \(\mu_v=N_v/N\) does not provide a meaningful downward bridge from a discrete resident problem: the original paper already had no \(N\)-resident formulation, and expanding \(N_v\) residents merely repeats the same indivisible site. Thus the alleged high-multiplicity regime compresses an invented population parameter rather than the paper’s computational input.
Theorem 14 suffers from exactly the same defect. Its weighted version is a legitimate weighted graph problem, but not a population continuization in the programme’s stronger sense. The uniform subfamily reproduces the original NP-complete problem, while nonuniform masses merely give weighted connected partitioning. The two anchors consequently differ only in whether charity is permitted; they do not expose two distinct population-computational phenomena.
There is a sharper dilemma for any improved mirror. If site populations remain indivisible, the model is just weighted graph partitioning, with the “society” serving as passive vertex weights. If populations at a site may be divided among districts, then the model no longer preserves the paper’s node-partition problem: precincts or goods may belong to several parts. On trees and other connected structures, fractional boundary assignments can often equalize mass directly, turning the central obstruction into a divisible-resource connected-allocation problem rather than a continuation of the paper’s hardness results. Preserving both the atomic graph problem and a genuinely operative continuous population is therefore difficult.
This negative case is ultimately weaker than the brief demands. The redistricting interpretation is plausible, repeated residents at a site are a valid high-multiplicity construction, and the weighted problems are formally well posed. Moreover, the programme explicitly regards hardness surviving on the uniform subfamily as a worthwhile Class B outcome. So one cannot honestly dismiss the anchors merely because the continuous version remains hard or because it resembles weighted graph partitioning. The best defensible conclusion is conditional: reject these mirrors if ChoCo requires population mass to be an allocatable computational object; under the programme’s broader definition, Theorems 13 and 14 survive as legitimate, if structurally conservative, continuous mirrors.
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.