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:

Construction

Given an independent set instance with and , let

Create one candidate for every vertex :

Construct the voters as follows:

1. For every edge , create one edge voter with approval set
2. For every vertex , create private voters, each with approval set

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

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

Score Formula

For , write

and let

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

The target is reached exactly when is independent.

Correctness

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

Correctness

Forward

Suppose that has an independent set with . Choose a subset with and let be the corresponding committee. Since is independent,

The score formula gives

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

Backward

Suppose that a size- committee has score at least . The score formula gives

Thus the threshold can be reached only when . No two vertices of are adjacent, so is an independent set of size and is a yes-instance.

Running Time

The construction creates candidates, edge voters, and

private voters. Since when has an edge, and otherwise, the output has polynomial size. The graph degrees, private voters, approval sets, and threshold 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.