Recall the 3-SAT problem. Given a collection of 3-literal clauses, we want to decide whether there is a assignment (of true/false values to variables) that satisfies each clause. This problem is NP-complete even if we assume that clauses cannot contain the same variable multiple times. For instance, clauses (x_1 x_1 x_1) or (x_1 x_1 x_2) are not allowed. The number of occurrence of a variable x_i in the instance of 3-SAT is the number of times literals x_i or x_i appears in the instance. For example, in instance (x_1 x_1 x_1) (x_6 x_1 x_4) A (x_1 x_1 x_1) A (x_2 x_3 x_5) there is 1 occurrence of x_1, 3 occurrences of x_2, 3 occurrences of x_3, 1 occurrence of x_1 2 occurrences of x_5, and 2 occurrences of x_6. A bipartite graph is a undirected graph G = (V, E) in which vertices can be partitioned into two sets V_1, V_2 (so V_1, union V_2 = V and V_1 Intersection V_2 = {}) such that every edge (u, v) element E has one end point in V_1 and the other end point in V_2. A bipartite graph is often denoted as G = (V_1, V_2, E). A graph is called regular, if every vertex has the same degree. For example, the following graph is a regular bipartite graph: Given a bipartite graph G = (V_1, V_2, E). Find a maximal matching E' E. (Recall: no two edges in a matching share a vertex.) The BIPARTITE MATCHING problem can be solved in time O(|V||E|) by Ford-Fulkerson algorithm. In addition, we have the following theorem: A regular bipartite graph has a matching with exactly |V_1| = |V_2| edges (so it involves all vertices). Consider a special version of 3-SAT that requires that each variable has exactly 3 occurrences and no clause can contain multiple occurrences of the same variable. Let's call this problem 3-SAT3. Show that 3-SAT3 can be solved in polynomial time by reducing it to the BIPARTITE MATCHING problem. Determine the running time of your algorithm! Recall the 3-SAT problem. Given a collection of 3-literal clauses, we want to decide whether there is a assignment (of true/false values to variables) that satisfies each clause. This problem is NP-complete even if we assume that clauses cannot contain the same variable multiple times. For instance, clauses (x_1 x_1 x_1) or (x_1 x_1 x_2) are not allowed. The number of occurrence of a variable x_i in the instance of 3-SAT is the number of times literals x_i or x_i appears in the instance. For example, in instance (x_1 x_1 x_1) (x_6 x_1 x_4) A (x_1 x_1 x_1) A (x_2 x_3 x_5) there is 1 occurrence of x_1, 3 occurrences of x_2, 3 occurrences of x_3, 1 occurrence of x_1 2 occurrences of x_5, and 2 occurrences of x_6. A bipartite graph is a undirected graph G = (V, E) in which vertices can be partitioned into two sets V_1, V_2 (so V_1, union V_2 = V and V_1 Intersection V_2 = {}) such that every edge (u, v) element E has one end point in V_1 and the other end point in V_2. A bipartite graph is often denoted as G = (V_1, V_2, E). A graph is called regular, if every vertex has the same degree. For example, the following graph is a regular bipartite graph: Given a bipartite graph G = (V_1, V_2, E). Find a maximal matching E' E. (Recall: no two edges in a matching share a vertex.) The BIPARTITE MATCHING problem can be solved in time O(|V||E|) by Ford-Fulkerson algorithm. In addition, we have the following theorem: A regular bipartite graph has a matching with exactly |V_1| = |V_2| edges (so it involves all vertices). Consider a special version of 3-SAT that requires that each variable has exactly 3 occurrences and no clause can contain multiple occurrences of the same variable. Let's call this problem 3-SAT3. Show that 3-SAT3 can be solved in polynomial time by reducing it to the BIPARTITE MATCHING problem. Determine the running time of your algorithm
