Problem:
You have $$$n$$$ radio channels and $$$m$$$ conditions about them. ($$$1 <= n,m <= 100$$$).
You need to build exactly $$$2$$$ radio stations that have an equal number of radio channels and satisfy all the conditions.
A condition is in the form $$$A$$$ $$$B$$$ and it means that radio channels $$$A$$$ and $$$B$$$ can't be at the same radio station.
What is the minimum number of radio channels that will not belong in any radio station?
Example: $$$n = 5,m = 3$$$
Conditions:
$$$[4,2]$$$
$$$[3,4]$$$
$$$[5,1]$$$
The answer is $$$1$$$ since we can have the $$$1st$$$ radio station with radio channels $$$[1,4]$$$ and the $$$2nd$$$ radio station with radio channels $$$[2,5]$$$.
This problem is from a national competition in Cyprus. Can someone give a hint about the solution or maybe recommend a similar problem?
if i got the problem correctly, the answer should be 0. [1,2,3] [4,5] all radio channels belong to some radio station.
You need to build exactly 2 radio stations that have an EQUAL NUMBER of radio channels and satisfy all the conditions.
An undirected graph representation of this problem has $$$n$$$ node and $$$m$$$ edges, where each node $$$1 \leq u \leq n$$$ is assigned color $$$0$$$, $$$1$$$ or $$$2$$$ which denotes that node $$$u$$$ does not belong to any station; belongs to radio station $$$1$$$; or belongs to radio station $$$2$$$, respectively. The optimization problem is than to find the coloring scheme which minimizes the number of nodes with color $$$0$$$ while satisfying the following condition for each edge $$$(A,B)$$$, where $$$1 \leq A,B \leq n$$$ and $$$A\ne B$$$, in addition to the condition that the number of nodes with color $$$1$$$ is equal to the number of nodes with color $$$2$$$.
$$$color(A) \ne 0$$$ and $$$color(B) \ne 0$$$ $$$\implies color(A) \ne color(B)$$$.
The complexity of the brute-force exhaustive search optimization algorithm should be $$$O(m \times 3^n)$$$.
Another graph formulation of the problem is to find the best partitioning of the $$$n$$$ nodes into $$$3$$$ subsets $$$U$$$, $$$X$$$ and $$$Y$$$ that correspond to the subsets of all unassigned channels, channels that belong to radio station $$$1$$$, and channels that belong to radio station $$$2$$$, respectively. The optimal partition should satisfy that $$$|U|$$$ is minimum, $$$|X| = |Y|$$$, and no edge $$$(A,B)$$$ exists between two nodes in $$$X$$$ or two nodes in $$$Y$$$.
Yes, that's exactly the solution I came up with but I was looking for something faster. I also thought of a solution $$$O((n^2 + n + m) * 2^n)$$$ but it is still pretty slow.
The following observation may lead to faster solution: at least one channel has to be unassigned in any cycle of odd length in the graph, as assigning all the channels on the cycle to either station $$$1$$$ or station $$$2$$$ leads to violating the edge constraint at least once. The problem is then reduced to finding the minimum number of nodes that should be removed from the graph such that remaining graph has no odd-length cycles. The answer to the original problem should be equal to this number, $$$+1$$$ if the number of nodes in the remaining graph is odd.
This is not actually true because if you have a graph that has not have odd cycles then this doesn't mean that you can divide it into two groups of equal a size. However probably a greedy on this will work but still I don't know how to find the minimum number of vertices to delete to make the graph biprative.
Yes, you are right. BFS-based coloring of bipartite graphs does not guarantee that the two disjoint groups have the same size or different in size by at most $$$1$$$. The optimal answer should be equal to min [number of nodes to be removed so as to make the graph bipartite + abs(size(group[1])-size(group[2])) of the remaining colored bipartite graph].
Finding the minimum number of nodes to be removed from the graph so that the remaining graph is bipartite can be reduced to finding the minimum-size cover of all odd-length cycles in the original graph such that each odd-length cycle has at least one node that exists in this minimum-size cover.
Consider the following regular graph with $$$n = 2 k$$$ nodes $$$m = 4 k - 3$$$ edges, $$$k$$$ edges $$$(2i-1,2i)$$$ for $$$1 \leq i \leq k$$$, in addition to $$$3(k-1)$$$ edges: $$$(2i-1,2i+1)$$$, $$$(2i,2i+2)$$$ and $$$(2i,2i+1)$$$ for $$$1 \leq i \leq k-1$$$. It can be shown that an odd-length cycle passes through each node in the graph.