Find the Minimun Vertex Cover for a Tree

Problem: Given a tree, find its minimum vertex cover. Wait, what is a vertex cover? Given a undirected graph G(V,E),  a vertex cover is a subset of V such that for any egde e in E, at least one of e's two endpoints should be in this subset (vertex cover).

Solution: The minimum vertex cover for a general graph is a NP-hard problem. However, for a tree, there is a linear solution. The idea here is to do DFS search plus post-order traversal. If we encounter a leaf node and the edge connecting this leaf node with its parent, we know in order to construct a vertex cover, we must include at least one of the node (the leaf node, or its parent). Here we can use a greedy approach. We can see selecting the leaf doesn't give us any extra benefit, while selecting the parent can give us some benefit, since the parent must be also connected to other nodes. By selecting the parent node, we can further "cover" some extra edges. With this strategy in mind, our algorithm is as follow:

• we do a DFS search. When a DFS call on a child node returns, we check if the child and the parent are both unselected. If yes, we select the parent node.
• After all the DFS finishes (we traverse the tree), those selected nodes form the minimum vertex cover. The cost is O(N).

The pseudo code is as follow:

void min_vertex_cover(TreeNode *root)
{
   if(isLeaf(root)) return; 

   for(int i=0; i<root->num_of_children; i++)
   { 
        min_vertex_cover(root->children[i]);

        if(!root->selected && !root->children[i]->selected)
               root->selected = true;
         
   }
}

Find the Diameter of a Convex

Problem: Give a convex that contains n vertices, find its diameter, basically the pair of vertices that have the longest distance.

Solution: This is the essential problem to solve the more general problem: find the farthest pair of points among n points, but now let's focus on this problem. Assume the vertices of the convex are ordered counter-clockwise (clockwise is also OK) and they are labeled as v1, v2, ..., vn, we can use method that mimics "rotating the convex" to solve the problem in O(n).

First we need to introduce the concept of antipodal pair, the diameter must be the distance between one antipodal pair. Therefore, if we found all antipodal pairs, we can get the diameter. Then how to find all the antipodal pairs efficiently? The detail is as follow:

1. For edge vnv1 (the line that connects vn and v1), we follow the couter-clockwise order to find the vertex that is farthest from vnv1. We name it vk.  
2. Then we move to edge v1v2, again, we try to find the vertex that is farthest from v1v2. We name it vp. It is easy to see any vertex from vk to vp form an antipodal pair with v1, then we add the pairs (v1, vk), ... , (v1, vp) to our antipodal set.
3. Then we let vk = vp  and move to edge v2v3. Again try to find the vertex that is farthest from v2v3. This vertex will be the new vp. Repeat this process until we finish processing the edge vn-1vn.
4. Now we get all the antipodal pairs, just do a linear scan to find the maximum.

When calculating distance, we can used signed area which avoids square root calculation.

More: To solve the farthest pair of points problem, basically we first first the convex hull of these points, then we apply this convex diameter algorithm. The total cost is O(nlogn) which is dominated by the cost of finding convex hull.

Decide If a Point is Inside a Simple Polygon

Problem: Given a point x,  try to decide if x is inside a simple polygon P. P is denoted by its vertices {p1, p2, ... , pn} .

Solution: There exists an O(N) solution based on one important observation: any ray from x will cross the boundary of P for odd number of times if and only if x is inside P. Here a ray is a line start from a point. Before designing an algorithm based on this observation, there are two cases that we need to be cautious. One is when the ray across some vertices of P. Under such case, we need another way to  define the number of times that the ray across the boundary of P. The second case is when x is actually on the boundary of P, but this is easy to tell. Therefore, the skeleton of the algorithm looks as follows:

1. Decide if x is on the boundary of P, if so return True, otherwise return False. This step takes O(N) since there are N edges.
2. Find a ray that starts from x (we can just use a vertical ray and the ray can ends at the lowest y coordinate of the polygon + 1) , for each edge of P, check if the ray intersect with that edge. Each such operation takes O(1) and the total takes O(N).  Here we need to handle the special case where the ray across some vertices of P.  Assume i1, i2, ... , ik are the points at which the ray intersect the boundary, if any such point is not a vertex of P, then we define the number of times that the ray across the boundary of P as k. If any such point is a vertex of P, we define the number of times that the ray across the boundary of P as 1. For the rest, we  define the number of times that the ray across the boundary of P as num_of_non_vetex_points.

Find the Convex Hull

Problem: a series of points are on plain (X>0 and Y>0), find the convex hull of these points, a.k.a, the points which can form a hull that include all the other points.

Solution: Here only main idea is given.Basically we can use Graham scan.

• Find the point p0 with the smallest y coordinate; if multiple exist, choose the one with the smallest x coordinate, this point must be one of the vertices on the convex hull.
• Sort the other points based on the angle of p0->pi. 
• Put p0, p1 and p2 in a stack (we need at least three to form a hull), then we inspect the rest points based on the order. Assume px is the stack top and py is the one next to the top, if py->pi is at the right side of py->px, pop px. We apply the same check to the new px and py until the previous condition doesn't hold. Then we push pi if previous there are any pop operations. If before push pi, there are only two elements in stack, we can push pi directly. 
• After we iterate all the remaining points, the points on the stack are those that form the convex hull. The complexity is O(nlogn), primarily the sorting cost.

More: Alternatively, we can use Jarvis’s march which is asymptotically faster than Graham’s scan. The time complexity is O(nh) where h is the number of the vertices on the hull. The main idea is as follow:

• Find the highest point p_high and lowest point p_low among all the points, which takes O(n).
• Start from p_low, find the next point that has the smallest polar angle (using +x axis) with respect to p_low. Assume this point is p', then find the next point that has the smallest polar angle with respect to p'. Repeat such process until we find p_high. Up to now, we had found the left chain of the hull.
• Then proceed to find the right chain of the hull. It is similar to finding the left chain. We start from p_high and stop when we reach p_low. The only difference is that when we calculate the polar angle, we use -x axis instead of +x axis.

Maximum Flow and Minimum Cut Problem

Problem: Given a network that contains a single source and a single sink, find the maximum (aggregated) flow from the source to the sink. This is Maximum Flow problem.

Solution: The solution is as follow:

1. find a flow in which each edge has strictly positive capacity. Then find the bottleneck edge in the flow. Subtract each edge's capacity with the bottleneck edge's capacity. 
2. try to find another flow in which each edge has strictly positive capacity. Repeat step 1.
3. if such flow cannot be found, terminate. The maximum flow is the sum of all the capacity of the bottleneck edge of the flow processed. 

Minimum Cut problem is from Maximum Flow problem. Basically, first run maximum flow algorithm to find those bottleneck edges. Then the minimum cut is from those edges.

More: Maximum flow (minimum cut) is frequently used in the problem related to flow network. Some other problem which can be solved by (or converted to) maximum flow problem are maximum matching in bipartie graph, minimum path cover, etc.

See Also: Maximum Flow and Minimum Cut

Check If a Graph is a Bipartite Graph

Problem: Given a graph, check it is a bipartite graph. A bipartite graph is a graph whose vertices can be divided into two sets. Then for every edge, the vertices connected by the edge are distributed in the two different sets (can't be both in one set).

Solution: If is similar to a coloring problem. We can do a BFS traversal to the graph. We need some extra space to store i) if a vertex is visited ii) the parity of that vertex. Or we can just use two hash tables.

• start from any vertex in the graph, we mark that vertex as visited, its parity as 1. Then we set the parity of its neighbors as 2. Since all the neighbors are not visited now, we put them in a queue.
• remove a vertex from the queue, if it is visited, ignore it. Otherwise, mark it as visited, check all its visited neighbors, if the parities are all odd or even, then the graph is not bipartite. Otherwise, set the parity of its non-visited neighbors as i+1 (assume the current vertex's parity is i) and add non-visited vertices to the queue.
• repeat the above step util the queue is empty. If the graph is not fully connected, need one extra step to check if all the vertices are visited