Independent Set to Chamberlin-Courant Winner Determination (Karp Reduction)

Definition

Independent Set to Chamberlin-Courant Winner Determination

There is a polynomial-time many-one reduction from the Independent Set problem to the Chamberlin-Courant winner determination decision problem:

$$\mathrm{INDEPENDENT}\mathrm{SET}{\le }_m^p\mathrm{CC}\text{-}\mathrm{WD}.$$

Construction

Given an independent set instance $(G,k)$ with $G=(U,E)$ and $n=|U|$, let

$$D:=\max \left\{1,\underset{u\in U}{\max }{\mathrm{deg}}_G(u)\right\}.$$

Create one candidate $c_u$ for every vertex $u\in U$:

$$C:=\{c_u\mid u\in U\}.$$

Construct the voters as follows:

1. For every edge $e=\{u,v\}\in E$, create one edge voter with approval set $$A_e=\{c_u,c_v\}.$$
2. For every vertex $u\in U$, create $D-{\mathrm{deg}}_G(u)$ private voters, each with approval set $$\{c_u\}.$$

Repeated approval sets represent distinct voters. Output the Chamberlin-Courant decision instance with candidate set $C$, these voters, committee size $k$, and threshold

$$s:=Dk.$$

The private voters fill each vertex’s degree deficit. Consequently, every candidate is approved by exactly $D$ voters:

$${\mathrm{deg}}_G(u)+(D-{\mathrm{deg}}_G(u))=D.$$

Score Formula

For $S\subseteq U$, write

$$W_S:=\{c_u\mid u\in S\}$$

and let

$$E[S]:=\{\{u,v\}\in E\mid u\in S\wedge v\in S\}$$

be the edges induced by $S$. Every selected candidate contributes one approval incidence for each of its $D$ approving voters, so $W_S$ has $D|S|$ approval incidences. An edge voter with both endpoints selected is counted twice among these incidences but represents only one voter. Therefore

$${\mathrm{score}}_{\mathrm{CC}}(W_S)=D|S|-|E[S]|.$$

The target $D|S|$ is reached exactly when $S$ is independent.

Correctness

The graph $G$ has an independent set of size at least $k$ if and only if the constructed election has a size-$k$ committee with Chamberlin-Courant score at least $Dk$.

Correctness

Forward

Suppose that $G$ has an independent set $S$ with $|S|\ge k$. Choose a subset $S^{\prime }\subseteq S$ with $|S^{\prime }|=k$ and let $W_{S^{\prime }}$ be the corresponding committee. Since $S^{\prime }$ is independent,

$$E[S^{\prime }]=\varnothing .$$

The score formula gives

$${\mathrm{score}}_{\mathrm{CC}}(W_{S^{\prime }})=Dk.$$

Hence the constructed Chamberlin-Courant instance is a yes-instance.

Backward

Suppose that a size-$k$ committee $W_S$ has score at least $Dk$. The score formula gives

$${\mathrm{score}}_{\mathrm{CC}}(W_S)=Dk-|E[S]|\le Dk.$$

Thus the threshold can be reached only when $|E[S]|=0$. No two vertices of $S$ are adjacent, so $S$ is an independent set of size $k$ and $(G,k)$ is a yes-instance.

Running Time

The construction creates $n$ candidates, $|E|$ edge voters, and

$$\sum _{u\in U}(D-{\mathrm{deg}}_G(u))=nD-2|E|$$

private voters. Since $D\le n-1$ when $G$ has an edge, and $D=1$ otherwise, the output has polynomial size. The graph degrees, private voters, approval sets, and threshold $Dk$ can all be constructed in polynomial time.

NP-completeness

The reduction proves that Chamberlin-Courant winner determination is NP-hard. Together with membership in NP, established in the decision-problem note, this proves NP-completeness.