UVa 10982

Summary

This is a graph theory problem with a greedy solution.

We are given a graph ${\displaystyle G}$ with ${\displaystyle n}$ nodes, numbered from 1 to ${\displaystyle n}$, and ${\displaystyle 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 ${\displaystyle {\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:
else:
Output cut {A, B}


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

Proof: Let ${\displaystyle E_{i}}$ denote all edges (i, j) in which j<i. Clearly, ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 1,2,\dots ,i}$.)

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

Gotchas

• The same edge may be listed multiple times.

Input

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