A Little Charity Guarantees Fair Connected Graph Partitioning (aaai22-20420)

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\)?

Definitions. For \(X\subseteq V\), let \(\mu(X)=\sum_{v\in X}\mu_v\). A connected pseudo \(n\)-partition is a partition \(V=V_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}V_n\mathbin{\dot\cup}R\) with \(\lvert R\rvert\le n-1\), such that for every \(i\) there is \(R_i\subseteq R\) for which \(G[V_i\cup R_i]\) is connected.

Target. Is deciding whether there exists such a partition with
\(\max_i\mu(V_i)\le\min_i\mu(V_i)\) in \(\mathsf{P}\), or is it \(\mathsf{NP}\)-hard?

Nearest known results. The unweighted special case, in which every vertex has the same mass, is \(\mathsf{NP}\)-complete: deciding whether a balanced connected pseudo \(n\)-partition with at most \(n-1\) excluded vertices exists.

Classification

The weighted problem is \(\mathsf{NP}\)-hard, even when every vertex has mass \(1\). Under the standard binary encoding of integer or rational masses, it is in \(\mathsf{NP}\), and hence is \(\mathsf{NP}\)-complete.

Source problem

Consider the following unweighted problem:

Given \(G=(V,E)\) and \(n\), decide whether there is a connected pseudo \(n\)-partition
\[ V=V_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}V_n\mathbin{\dot\cup}R \]
with \(\lvert R\rvert\le n-1\) and
\[ \max_{i\in[n]}\lvert V_i\rvert\le \min_{i\in[n]}\lvert V_i\rvert. \]

Because the maximum of finitely many numbers is always at least their minimum, the last inequality is equivalent to
\[ \lvert V_1\rvert=\cdots=\lvert V_n\rvert. \]

This is precisely the balanced connected pseudo-partition problem stated as \(\mathsf{NP}\)-complete in Theorem \(13\) of [A Little Charity Guarantees Fair Connected Graph Partitioning](https://ojs.aaai.org/index.php/AAAI/article/download/20420/20179). The paper defines balancedness as \(1\)-balancedness, namely equality of the largest and smallest part sizes.

Polynomial reduction

Let \((G,n)\) be an instance of the unweighted problem. Construct an instance of the weighted problem on the same graph and with the same value of \(n\), assigning
\[ \mu_v=1 \]
to every \(v\in V\).

This transformation is computable in polynomial time. Moreover, for every \(X\subseteq V\),
\[ \mu(X)=\sum_{v\in X}1=\lvert X\rvert. \]

Consequently, for every structurally feasible pseudo \(n\)-partition,
\[ \max_{i\in[n]}\mu(V_i)\le\min_{i\in[n]}\mu(V_i) \]
holds if and only if
\[ \max_{i\in[n]}\lvert V_i\rvert\le\min_{i\in[n]}\lvert V_i\rvert. \]

The reduction does not modify \(G\), \(R\), or the connector condition. Thus the same sets \(R_i\subseteq R\) certify connectivity in both instances. Therefore,
\[ (G,n)\text{ is a yes-instance of the unweighted problem} \]
if and only if
\[ (G,n,(\mu_v)_{v\in V})\text{ is a yes-instance of the weighted problem}. \]

This is a polynomial-time many-one reduction from an \(\mathsf{NP}\)-complete problem. Hence the target problem is \(\mathsf{NP}\)-hard, already for unit masses.

Membership in \(\mathsf{NP}\)

Assume masses are nonnegative integers or rationals given in binary. A certificate consists of the sets \(V_1,\ldots,V_n,R\) and, for each \(i\), a set \(R_i\subseteq R\).

In polynomial time one can:

• Verify that \(V_1,\ldots,V_n,R\) form the required partition and that \(\lvert R\rvert\le n-1\).
• Verify \(R_i\subseteq R\) for every \(i\).
• Test connectivity of each induced graph \(G[V_i\cup R_i]\) by graph search.
• Compute each rational sum \(\mu(V_i)\) exactly and compare the resulting values.

Thus the problem belongs to \(\mathsf{NP}\). Combined with the reduction, it is \(\mathsf{NP}\)-complete under the standard finite encoding of masses.

⟨structured verdict parsed — rendered above⟩

Verification report

Overall assessment

The prover correctly establishes that the weighted problem is \(\mathsf{NP}\)-hard, even with unit masses. Under the explicitly stated binary encoding of integer or rational masses, the additional claim of \(\mathsf{NP}\)-completeness is also correct.

Step-by-step audit

• Source problem

The cited Theorem 13 indeed states that deciding the existence of a balanced connected pseudo \(n\)-partition with at most \(n-1\) excluded vertices is \(\mathsf{NP}\)-complete. The paper’s connector condition also matches the condition in the task: for every \(i\), some \(R_i\subseteq R\) makes \(G[V_i\cup R_i]\) connected. [A Little Charity Guarantees Fair Connected Graph Partitioning](https://ojs.aaai.org/index.php/AAAI/article/download/20420/20179)

• Interpretation of balancedness

For a nonempty finite family \((|V_i|)_{i\in[n]}\), one always has
\[ \max_i |V_i|\geq \min_i |V_i|. \]
Therefore the reverse inequality used in the decision condition holds exactly when all part sizes are equal. This correctly matches the cited notion of exact balancedness.

• Reduction

Assigning \(\mu_v=1\) for every vertex is a polynomial-time transformation. For every \(X\subseteq V\),
\[ \mu(X)=|X|. \]
Hence the weighted equality condition is equivalent to the unweighted balancedness condition for every candidate partition.

The graph, the number of parts, the excluded set, and all connector witnesses remain unchanged. Thus the reduction preserves both yes-instances and no-instances. This is a valid polynomial-time many-one reduction.

• Hardness conclusion

Since the source problem is \(\mathsf{NP}\)-complete, the reduction proves \(\mathsf{NP}\)-hardness. The hardness holds on the restricted class of instances having only unit masses, so it also holds for the general weighted problem.

• Membership in \(\mathsf{NP}\)

Under binary-encoded integer or rational masses, the proposed certificate is sufficient. Partition validity, the exclusion bound, connector containment, and induced-subgraph connectivity are all polynomial-time checkable.

Exact sums of binary rationals have polynomially bounded representation length relative to the total input length, so their comparison is polynomial-time computable. The certificate size is also polynomial on potentially feasible instances, since connected parts are nonempty and hence \(n\leq |V|\).

• Encoding scope

The prover correctly qualifies the \(\mathsf{NP}\)-membership and \(\mathsf{NP}\)-completeness assertions by requiring a standard finite encoding. The \(\mathsf{NP}\)-hardness conclusion itself does not depend on a broader encoding convention because it already holds for the exactly representable mass \(1\).

Issues

No mathematical, logical, or scope defects were found.

⟨structured verdict parsed — rendered above⟩