UVa 10982

From Algorithmist
Jump to navigation Jump to search

10982 - Troublemakers[edit]

Summary[edit]

This is a graph theory problem with a greedy solution.

We are given a graph with nodes, numbered from 1 to , and 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 .

Explanation[edit]

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 denote all edges (i, j) in which j<i. Clearly, are disjoint sets, whose union is E (all edges). At the i-th step the algorithm considers only edges of , 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 .)

The algorithm adds i-th vertex to set A when , and to set B when , so exactly edges of will be in the cut. Since , it follows that . Hence, the final size of the cut is at least , as required.


Gotchas[edit]

  • The same edge may be listed multiple times.

Input[edit]

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[edit]

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