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:

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 proportional approval voting 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 . A selected candidate has approval incidences. The PAV contribution of a voter depends on how many of the voter’s approved candidates are selected:

selected approved candidates
voter contribution

Every selected candidate supplies a base contribution of through each of its approving voters, giving . If an edge has both endpoints in , its edge voter receives instead of the base value , losing . Thus

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 PAV 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 proportional winner determination instance is a yes-instance.

Backward

Suppose that a size- committee has PAV 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 proportional winner determination is NP-hard. Together with membership in NP, established in the decision-problem note, this proves NP-completeness.