Independent Set to Proportional Winner Determination (Karp Reduction)

Definition

Independent Set to Proportional Winner Determination

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

$$\mathrm{INDEPENDENT}\mathrm{SET}{\le }_m^p\mathrm{PAV}\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 proportional approval voting 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$. A selected candidate has $D$ approval incidences. The PAV contribution of a voter depends on how many of the voter’s approved candidates are selected:

selected approved candidates	$0$	$1$	$2$
voter contribution	$0$	$1$	$1+\frac{1}{2}=\frac{3}{2}$

Every selected candidate supplies a base contribution of $1$ through each of its $D$ approving voters, giving $D|S|$. If an edge has both endpoints in $S$, its edge voter receives $\frac{3}{2}$ instead of the base value $2$, losing $\frac{1}{2}$. Thus

$${\mathrm{score}}_{\mathrm{PAV}}(W_S)=D|S|-\frac{1}{2}|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 PAV 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{PAV}}(W_{S^{\prime }})=Dk.$$

Hence the constructed proportional winner determination instance is a yes-instance.

Backward

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

$${\mathrm{score}}_{\mathrm{PAV}}(W_S)=Dk-\frac{1}{2}|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 proportional winner determination is NP-hard. Together with membership in NP, established in the decision-problem note, this proves NP-completeness.