[C Program]
a Reductions and Boolean Satisfiability I (Split graphs recognition) Boolean satisfiability (SAT) is, as far as Computer Scientists know, a hard problem. We will define precisely what we mean by this later on in the course. This problem is defined as follows: The input is a collection of m clauses over n boolean variables X1, X2, ... Xn. Each clause is a disjunction of some of the variables or their complements. The problem consists in answering the question "Is there a way to assign truth values to each variable that makes every clause of the instance TRUE? For instance, here is an instance of SAT made of 4 clauses over 3 variables: 1. XV X3 2. XV XV X3 3. X2 X3 4. X3 Equivalently, you could think of this instance as the single boolean expression (X1V X3) (XVX2 V X3) (X2 V X3) A X3 There are many other problems whose level of difficulty is similar to that of Boolean Satisfiability, and this problem has attracted a lot of research. So while the problem is difficult to solve in general, a number of tools to solve instances of the problem have been developed (see the Wikipedia page for details and links). We can take advantage of these tools to solve other problems using reductions. In this question, we will look at the problem of determining whether or not a graph is a split graph. A graph G = (V, L) is a split graph if we can partition its vertex set V into two subsets V1, V2 such that V = V UV2, Vin V2 = %, every two vertices of Vi are connected by an edge (Vu E V1, VW V1, {v, w} E) and no two vertices of V2 are connected by an edge (Vv E V2, VW E V2,{v,w} &E). For instance, the following graph is a split graph, where the vertices of Vi are colored Red, and the vertices of V2 are colored Blue. B3 B4 B5 R1 R2 B2 R3 B6 RO B1 R4 1. (3 points) Show how to reduce a arbitrary instance of the split graph recognition problem into an instance of Boolean Satisfiability (SAT). Ilint: you will want to introduce a single variable for each vertex of the graph. 2. [1 point] Write the collection of clauses you would get for the following graph: 3. [2 points) What is the length of the instance of SAT that your algorithm generates, as a function of the number n of vertices, and the number m of edges of the input graph G? 4. [3 points) Explain briefly why, if an input graph is a split graph, then there is a way to assign values to the variables in the instance of SAT that makes every clause TRUE. 5. (3 points) Explain briefly why, if there is a way to assign values to the variables in the instance of SAT that makes every clause TRUE, then the graph used to generate the instance must be a split graph. Show how you would determine which vertices of G belong to which of the two subsets of V
