UVa 10982

Summary

This is a graph theory problem with a greedy solution.

We are given a graph $G$ with $n$ nodes, numbered from 1 to $n$ , and $m$ edges, and we want to partition the graph into two partitions such that the number of edges which are contained by two nodes in the same partition is at most ${\frac {m}{2}}$ .

Explanation

In graph theory terms, a partition of graph's vertices into two disjoint sets is called a cut. Size of a cut is defined as the number of edges, which have endpoints in both partitions. So, what we are really looking for in this problem, is a cut of size at least m/2. This can be done greedily. A related problem of finding a cut of largest possible size (MAX-CUT problem) is NP-hard.

The simplest solution is to randomly split vertices into two partitions (repeating this several times, if needed.) Expected size of a cut is m/2 edges, so with high probability this algorithm will quickly find desirable cut. There are also several deterministic algorithms, which show that such cut always exists.

Consider the following greedy algorithm:

A = {}, B = {}
for i = 1 to n:
a = 0, b = 0
for j = 1 to i-1:
if there is an edge (i, j):
if j is in A:
a++
else:
b++

if a <= b:
add x to set A
else:
add x to set B
Output cut {A, B}

Claim: The algorithm outputs a cut of size at least m/2.

Proof: Let $E_{i}$ denote all edges (i, j) in which j<i. Clearly, $E_{1},\dots ,E_{n}$ are disjoint sets, whose union is E (all edges). At the i-th step the algorithm considers only edges of $E_{i}$ , and computes values a and b -- the number of edges which connect vertex i with vertices in sets A and B respectively (Note, that at the i-th step {A, B} is a valid cut of subgraph of G, which contains vertices $1,2,\dots ,i$ .)

The algorithm adds i-th vertex to set A when $a\leq b$ , and to set B when $a>b$ , so exactly $\max(a,b)$ edges of $E_{i}$ will be in the cut. Since $a+b=|E_{i}|$ , it follows that $\max(a,b)\geq {\frac {|E_{i}|}{2}}$ . Hence, the final size of the cut is at least $\sum _{i=1}^{n}{\frac {|E_{i}|}{2}}={\frac {m}{2}}$ , as required.

Gotchas

• The same edge may be listed multiple times.

10
4 3
1 2
2 3
3 4

4 6
1 2
1 3
1 4
2 3
2 4
3 4

3 0

3 1
1 2

3 1
1 3

3 2
1 2
1 3

3 1
2 3

3 2
1 2
2 3

3 2
1 3
2 3

3 3
1 2
1 3
2 3

Output

Note the output is not unique.

Case #1: 2
2 4
Case #2: 2
3 4
Case #3: 3
1 2 3
Case #4: 2
2 3
Case #5: 2
2 3
Case #6: 2
2 3
Case #7: 2
1 3
Case #8: 1
2
Case #9: 1
3
Case #10: 2
2 3