Problem Link
Authors and Testers: Aditya Sarode and Vaibhav Tulsyan
Difficulty
Easy-Medium
Pre-requisites
Bit-masking, Graph Theory
Problem
When a node is coloured red, all its neighbours are colored red.
Given a graph, select minimum number of nodes such that all nodes in the graph are colored red.
Quick Explanation
Since the number of nodes is <= 20, create a bitmask for each node representing the adjacency list of each node - if the i^{th} node is a neighbour of a node, the i^{th} bit in the bitmask should be set.
Iterate over all 2^n combinations of selecting nodes. Perform Bitwise OR of adjacency lists of all selected nodes - if the first n bits are set after ORing the adjacency lists, check if the number of selected nodes is minimum.
Detailed Explanation
Bit-masking is a useful pre-requisite to solve this problem.
The problem is popularly known as the Dominating Set problem.
Let us consider all subsets of nodes that can be selected one-by-one in order to try to find a subset of nodes that satisfy the required conditions.
For testing validity of each subset, maintain a boolean array to mark a node if it gets visited.
As soon as all nodes of the subset and their neighbours are visited, iterate over the boolean array to check if all nodes of the graph have been visited or not.
We must pick the valid subset with minimum size.
There are 2^n subsets that need to be checked. For each subset, we iterate over all edges of the nodes present in the subset. Hence, the worst-case complexity of the algorithm would be O(2^n * m).
This would TLE on the last subtask.
However, this would give only 40 points.
So, how can the solution be optimized further?
Note that the maximum number of nodes present in the graph can be at most 20.
Hence, we can use a 32-bit int to maintain the adjacency list of each node. Thus, the adjacency list of each node can be represented by a 32-bit int. Hence, the graph can be represented by an integer array with n elements, where n is the number of nodes in the graph.
We can call this bitmask-adjacency-list as adjacency number.
If node j is a neighbour of node i, we set the j^{th} bit of the i^{th} element in the array to 1.
Now, we use the same technique of iterating over all subsets of nodes that can be selected.
Instead of maintaining a boolean array while checking the validity of a subset, we can use a 32-bit int to maintain how many nodes of the graph have been colored red.
Let this 32-bit int that maintains the red-colored nodes be X.
While iterating over a subset, we update X by doing bitwise-OR of X with the adjacency number of the current node in the subset.
X |= A_i, where A_i represents that the i^{th} node of the graph is being selected in the current subset.
Checking if X equals 2^n - 1 would suffice to check if all nodes are colored in the graph or not.
Complexity: O(2^n * n)