A Study on Generalized SolutionConcepts in Constraint Satisfactionand Graph ColouringbyPeng ZhangB.Eng, East China Normal University, 2010A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Interdisciplinary Studies)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)July 2014c© Peng Zhang, 2014AbstractThe concept of super solutions plays a crucial role in using the con-straint satisfaction framework to model many AI problems under uncertain,dynamic, or interactive environments. The availability of large-scale, dy-namic, uncertain, and networked data sources in a variety of applicationdomains provides a challenge and opportunity for the constraint program-ming community, and we expect that super solutions will continue to attracta great deal of interest. In the first part of this thesis, we study the prob-abilistic behaviour of super solutions of random instances of Boolean Satis-fiability (SAT) and Constraint Satisfaction Problems (CSPs). Our analysisfocuses on a special type of super solutions, the (1,0)-super solutions. Forrandom k-SAT, we establish the exact threshold of the phase transition ofthe solution probability for the cases of k = 2 and 3, and we upper andlower bound the threshold of the phase transition for the case of k ≥ 4.For random CSPs, we derive a non-trivial upper bound on the threshold ofphase transitions.Graph colouring is one of the most well-studied problems in graph theory.A solution to a graph colouring problem is a colouring of the vertices suchthat each colour class is a stable set. A relatively new generalization ofgraph colouring is cograph colouring, where each colour class is a cograph.Cographs are the minimum family of graphs containing a single vertex andare closed under complementation and disjoint union. We define the cog-chromatic number of a graph G as the minimum number of colours neededby a cograph colouring of G. Several problems related to cograph colouringare studied in the second part of this thesis, including properties of graphsthat have cog-chromatic number 2; computational hardness of deciding andapproximating the cog-chromatic number of graphs; and graphs that arecritical in terms of cog-chromatic numbers. Several interesting constructionsof graphs with extremal properties with respect to cograph colouring are alsopresented.iiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . viiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.1 Threshold phenomena of super solutions in CSPs . . . . . . . 11.2 Partitioning graphs into cographs . . . . . . . . . . . . . . . . 31.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4Chapter 2: Super solutions for random k-SAT and CSPs . . . 62.1 (1, 0)-super solutions for k-SAT . . . . . . . . . . . . . . . . . 62.2 Random models of k-SAT . . . . . . . . . . . . . . . . . . . . 72.3 The second moment method . . . . . . . . . . . . . . . . . . . 82.4 The threshold for (1,0)-2-SAT . . . . . . . . . . . . . . . . . . 102.5 The threshold for (1,0)-3-SAT . . . . . . . . . . . . . . . . . . 112.5.1 Lower bound on the threshold for (1, 0)-3-SAT . . . . 112.5.2 Upper bound on the threshold for (1, 0)-3-SAT . . . . 122.6 The threshold for (1,0)-k-SAT . . . . . . . . . . . . . . . . . . 152.7 Designing SAT benchmarks by projections . . . . . . . . . . . 192.8 Super solutions for random binary CSPs . . . . . . . . . . . . 21Chapter 3: Partitioning of graphs into cographs . . . . . . . . 253.1 Graphs and graph colouring . . . . . . . . . . . . . . . . . . . 253.2 Cographs and the cog-chromatic number . . . . . . . . . . . . 273.3 Approximating the cog-chromatic number . . . . . . . . . . . 31iiiTABLE OF CONTENTS3.3.1 Greedy colouring . . . . . . . . . . . . . . . . . . . . . 313.3.2 Maximum induced cograph . . . . . . . . . . . . . . . 333.3.3 Approximation algorithms . . . . . . . . . . . . . . . . 353.4 Minimum order of k-cog-chromatic graphs . . . . . . . . . . . 363.5 Cog-critical graphs . . . . . . . . . . . . . . . . . . . . . . . . 403.5.1 Properties of cog-critical graphs . . . . . . . . . . . . . 403.5.2 Arbitrarily large k-cog-critical graphs . . . . . . . . . 42Chapter 4: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 52Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53ivList of TablesTable 2.1 Upper bound and lower bound for (1, 0)-k-SAT . . . . 19vList of FiguresFigure 2.1 k = 5, r = 1, 1.2, 1.6, 2, 2.4, 2.8, 3.2 (top down) . . . . 19Figure 2.2 Experimental results on (1,0)-super solutions of ran-dom 4-CNF formula, where r = m/n is the clause-to-variable ratio and n = 500. . . . . . . . . . . . . . . . 20Figure 3.1 A vertex-minimal non-cograph+v graph . . . . . . . . 29Figure 3.2 Reduction from 3-SAT to χ(G) = 3 . . . . . . . . . . 30Figure 3.3 Worst case example of greedy P4-free colouring . . . . 32Figure 3.4 Reduction from Stable Set to Cograph problem . 34Figure 3.5 A graph J of c(J) = 3 with 10 vertices . . . . . . . . 38Figure 3.6 Another view of graph J of c(J) = 3 with 10 vertices 40viAcknowledgementsCompleting this thesis would have been impossible without the help ofYong Gao, Donovan Hare and James Nastos. The greatest mathematicalinfluence was from my supervisors, Yong Gao and Donovan Hare, and hasbeen invaluable. Besides my supervisors, I would like to give special thanksto James Nastos, for his help on the problems with cographs.viiChapter 1IntroductionThe constraint satisfaction problem (CSP) and graph colouring are im-portant problems in theoretical computer science and graph theory. Supersolutions and cograph colouring are generalizations to the standard solutionconcepts for CSPs and graph colouring respectively. In addition to theircombinatorial interest, these solution concepts also have potential real-worldapplications. For example, super solutions can be used to model problemsin Artificial Intelligence (AI) arising in dynamic or uncertain environments.Cograph colouring, also called cograph partitioning, may provide an alter-native approach to graph clustering and community structures in networkanalysis. Graph clustering [49] studies the problem of finding sets of “re-lated” vertices in graphs, while the analysis of community structures [44]deals with how to group nodes in a network into application-specific com-munities, such as densely connected subgraphs.1.1 Threshold phenomena of super solutions inCSPsDynamic CSPs have been used to model many problems arising in un-certain, dynamic, or interactive environments. For a dynamic CSP, it isdesirable to find solutions that can be modified at a low cost in responseto changes in the environment. This requires that a solution is not onlysatisfying, but also has a certain degree of robustness or stability. Thereare two typical approaches to dynamic CSPs, the reactive approach and theproactive approach [53]. In the reactive approach, one aims at finding a so-lution that can be easily “repaired” if it is no longer satisfying in a changedenvironment. In the proactive approach, a solution is required to be robustin the sense that there always exist solutions that are close to it.The super solution framework [26, 34] is a viable approach to formalizethe notion of a robust or stable solution. An (a, b)-super solution of a CSPinstance is a satisfying solution such that, if the values assigned to any set ofa variables are no longer available, a new solution can be found by reassign-11.1. Threshold phenomena of super solutions in CSPsing values to these a variables and at most b other variables. The availabilityof large-scale, dynamic, uncertain, and networked data sources in many ap-plication domains provides a challenge and opportunity for the constraintprogramming community [45]. To address the challenge, we expect thatconcepts of robust and stable solutions, such as fault-tolerant models [48]and super-solutions [34], will continue to attract a great deal of interest [12].Threshold phenomena is first observed by Erdo¨s and Re´nyi in their semi-nal work on random graphs [20]. Let G(n, p) be a random graph on n verticeswhere each edge exists with probability p. A sequence of events En occurswith high probability (w.h.p.) if limn→∞ P[En] = 1. It has been shown thatfor many interesting graph properties P , the probability for G(n, p) to haveP changes drastically at a certain critical value of p. This critical value orrange of p is called the threshold with respect to the property P . For exam-ple, when p = o( lognn ), a random graph is disconnected w.h.p., while whenp = ω( lognn ), a random graph is connected w.h.p. Threshold phenomena arealso found in many other random models. For example, threshold behaviourof the solution probability of random SAT and CSPs has been intensivelystudied theoretically and empirically since 1990s, [2–4, 10, 17, 21, 54].In general, finding super solutions to SAT and CSPs is NP-complete.In the AI and theoretical computer science literature, one of the fruitfulapproaches to understand the typical-case complexity of a hard problem is tostudy the probabilistic behaviour of random instances [4, 27]. By analysingthe threshold phenomena of the solution probability and the correlated easy-hard-easy pattern of the instance hardness of the standard solution conceptfor SAT and CSPs, much insight has been gained on the effectiveness ofmany heuristics widely used to tackle these problems [15, 22, 27].The first part of this thesis focuses on the probabilistic behaviour of supersolutions for random instances of SAT and CSPs. Our analysis focuses ona special (but highly non-trivial) type of super solutions, the (1,0)-supersolutions. A solution is a (1,0)-super solution if it is resistant to changesof any one variable. That is, for a (1,0)-super solution σ, there is alwaysanother solution σ′ such that σ′ and σ have different values on one variable.We denote the problems of finding (1, 0)-super solution for k-SAT and CSPsby (1, 0)-k-SAT and (1, 0)-CSP respectively. We find exact thresholds for thephase transition of (1, 0)-super solutions for random 2-SAT and 3-SAT. Asfor k ≥ 4, we establish upper and lower bounds on the threshold of random(1, 0)-k-SAT. We also establish a non-trivial upper bound on the thresholdof random (1, 0)-binary CSPs.21.2. Partitioning graphs into cographs1.2 Partitioning graphs into cographsStarting from a single vertex, cographs are recursively defined by graphoperations of disjoint union and complementation [40]. There are manyinteresting properties of cographs, such as not containing an induced path onfour vertices, the existence of a unique tree representation, and the existenceof a linear-time recognition algorithm. Partitioning graphs into cographs isa relatively new generalization of the well-known graph colouring problem.Thus, we call it graph cog-colouring. Colouring graphs into cographs hasbeen studied in [1, 8, 25, 35]. The first section of [25] provides an interestingand motivating axiomatization for many generalizations of graph colouring,including cog-colouring.Many difficult questions from the study of classic graph colouring havecounterparts worthy of study in the context of graph cog-colouring. Rec-ognizing graphs that can be partitioned into k cographs is proved to beNP-complete for any k ≥ 2 in [1]. Define the cog-chromatic number of agraph G to be the smallest possible k such that G can be partitioned into kcographs and denote it by c(G). A graph G is k-cog-colourable if c(G) ≤ kand is k-cog-chromatic if c(G) = k, where k ≥ 1. A variety of boundsand computational complexity questions regarding the cog-chromatic num-ber of graphs with different properties and computational complexity ques-tions have been studied [25]. For example, for any triangle-free graph G,c(G) ≤ χ(G) ≤ 2 · c(G), where χ(G) is the chromatic number of G. Anotherexample is that, for any planar graph G with girth at least 11, c(G) ≤ 2.It is also shown that, deciding cog-chromatic numbers is very hard, even onvery restricted graphs. For example, the following two decision problemsare NP-complete: (1) deciding c(G) ≤ 2 for a planar graph G of maximumdegree 6; (2) deciding c(G) ≤ k, k ≥ 2, for a chordal graph G. However, itis linear time to decide χ(G) ≤ 2 for any graph G and it is polynomial timesolvable to determine χ(G) for any chordal graph G [23].The second part of this thesis studies the cog-chromatic number. We firststudy 2-cog-colourable graphs. P4-sparse graphs and split-perfect graphs areshown to be 2-cog-colourable. We also prove that graph colouring is NP-hard on 2-cog-chromatic graphs. Since the k-cog-colourability is NP-hard todetermine for any k ≥ 2, we try to approximate the cog-chromatic numberfor graphs. Though we believe it is computationally hard to approximatec(G) for a general graph G, we do not have a proof. We consider twogreedy strategies of cograph colouring, one is based on lists of vertices andthe other repeatedly colours a maximum induced cograph in a new colour.An algorithm of partitioning graphs into at most d∆+12 e cographs is found,31.3. Overviewwhere ∆ is the largest degree of vertices in the graph. Finally, we studyhow to construct k-cog-chromatic graphs that satisfy several conditions. Forexample, we find a way of creating a graph G with O(2k) vertices and c(G) =k. A graph G is cog-critical if any vertex-deletion decreases its cog-chromaticnumber. A cog-critical graph G is k-cog-critical if c(G) = k. We find twodifferent constructions to create k-cog-critical graphs with arbitrarily manynumber of vertices, for any fixed k ≥ 3.1.3 OverviewIn Chapter 2, we analyse a special (but highly non-trivial) type of supersolutions, the (1,0)-super solutions. In Section 2.1, we discuss our obser-vation on the equivalence between a (1, 0)-k-SAT and a standard satisfyingsolution of a properly-constructed (k − 1)-SAT instance, which plays a cru-cial role in our analysis of the threshold behaviour of (1,0)-super solutions.In Section 2.4 and Section 2.5, we prove exact thresholds for the phase tran-sition of (1, 0)-super solutions for random 2-SAT and 3-SAT by making useof the equivalence presented in Section 2.1. In order to bound the prob-ability of satisfiable 2-SAT, we use a sufficient condition and a necessarycondition of satisfiability of 2-SAT proposed in [11]. However, our analysisis more involved than theirs because we have to handle the dependenciesintroduced in the translated equivalent SAT instances. For k > 3, we donot have any sufficient or necessary condition of satisfiability of k-SAT thatare strong enough to be used to prove thresholds. Therefore, we have to digdeeper and try to study the distributions of (1, 0)-super solutions. The tech-nique developed in [3] and [4] enables us to have a peek at the distributionof solutions and design weights on different solutions such that thresholdscan be proved. This technique of weighting solutions is so powerful thatthe long standing gap between upper bound and lower bound of thresholdsfor satisfiability of k-SAT is almost closed [4]. We apply this technique inSection 2.6 and establish upper and lower bounds on the threshold of ran-dom (1, 0)-k-SAT for k ≥ 4. Finally, in Section 2.8, we establish an upperbound on the threshold of random (1, 0)-binary CSPs. Our analysis of thethreshold for (1, 0)-CSP is very complicated and the results are not verysatisfying. We think that more advanced tools may be needed for analysingsuper solutions for random CSPs.In Chapter 3, we study the problem of partitioning graphs into cographs.We first study properties of 2-cog-colourable graphs in Section 3.2. We findthat P4-sparse graphs, split-perfect graphs are subclasses of 2-cog-colourable41.3. Overviewgraphs. We prove that deciding the chromatic number of k-cog-colourablegraphs is NP-complete for any fixed k ≥ 2. In Section 3.3, we try dif-ferent ways of partitioning 2-cog-colourable graphs into as small number ofcographs as possible. We study the bad performance of greedy colouring andhow to find maximum induced cographs from k-cog-colourable graphs. Wemove on to study the size of k-cog-chromatic graphs with the smallest num-ber of vertices in Section 3.4. We find a construction which is more efficientthan the one in [25] and conjecture that the smallest k-cog-chromatic graphhas O(2k) vertices. Finally and most interestingly, we discuss cog-criticalgraphs in Section 3.5. We give two nice ways of constructing k-cog-criticalgraphs G with arbitrary number of vertices, for any fixed k ≥ 3.5Chapter 2Super solutions for randomk-SAT and CSPsIn this chapter, we study the probabilistic behaviour of the (1, 0)-supersolution for random k-SAT and random binary CSPs. Let X = {x1, · · · , xn}be a set of n boolean variables. A literal is a variable or its negation. Ak-clause is a disjunction of k different literals and a k-CNF formula is aconjunction of some k-clauses. An assignment σ is a mapping σ : X →{1, 0}n and is said to satisfy a k-CNF formula F if each clause of F containsat least one literal that evaluates to true under σ. A satisfying assignmentis also called a solution.According to the definition of (a, b)-super solutions [34], a (1, 0)-supersolution for a k-SAT is a solution such that changing the value assigned toexactly one variable will not violate any clause. Equivalently, a (1, 0)-supersolution is an assignment such that every clause contains at least two literalsthat evaluate to true under the assignment.2.1 (1, 0)-super solutions for k-SATIn this subsection, we present a new equivalent condition for a (1, 0)-super solution, which plays a crucial role in our analysis.Definition 2.1 (Projection). The projection of a clause C = (l1 ∨ · · · ∨ lk)is defined to be T (C) = ∧ki=1(∨j 6=ilj)—the conjunction of the (k−1)-clausesin C. We say that C projects onto T (C) and call clauses in T (C) siblings.The projection of a CNF formula F is defined to be T (F ) = ∧Ci∈FT (Ci).For example, the projection of (x1∨x2∨x3) is (x1∨x2)∧(x1∨x3)∧(x2∨x3).For a k-clause C, its projection has k clauses of size (k − 1) and each such(k− 1)-clause is a (k− 1) combination from those k literals in C. Thus, if σsatisfies at least two literals of C, then σ must satisfy at least one literal ofeach (k− 1)-clause in the projection of C. Therefore, we have the followinglemma.62.2. Random models of k-SATLemma 2.2. An assignment (1,0)-satisfies F if and only if it satisfies T (F ).The following theorem complements existing results on the worst-casecomplexity of super solutions given in [34].Theorem 2.3. (1, 0)-k-SAT is in P for k ≤ 3, and is NP-complete other-wise.Proof. We can check whether an assignment is a (1, 0)-super solution of ak-CNF in O(k ·m) time, where m is the number of clauses. Thus, (1, 0)-k-SAT is in NP for any fixed k. Any instance of (1,0)-3-SAT F can be solvedby solving the 2-SAT instance of T (F ), which is in P. For k ≥ 4, we firstprove the NP-completeness of (1,0)-4-SAT via a reduction from 3-SAT. Notethat, σ satisfies (l1 ∨ l2 ∨ l3) if and only if it (1,0)-satisfies (l1 ∨ l2 ∨ l3 ∨ 1).For any 3-SAT F , we reduce it into a 4-SAT F ′ as following in three steps.First, create 4 additional variables, Y = {y1, y2, y3, y4} and a 4-SAT FY ofall the possible(42)clauses, where each clause has exactly two negations ofvariables.FY = (y1 ∨ y2 ∨ y3 ∨ y4) ∧ (y1 ∨ y3 ∨ y2 ∨ y4) ∧ (y1 ∨ y4 ∨ y2 ∨ y3)∧ (y2 ∨ y3 ∨ y1 ∨ y4) ∧ (y2 ∨ y4 ∨ y1 ∨ y3) ∧ (y3 ∨ y4 ∨ y1 ∨ y2)Secondly, for each clause ci in F , add c′i = (ci ∨ y1) into F ′. Finally, letF ′ be the conjunction of F ′ and FY . Note that, any assignment that (1,0)-satisfies FY must have σ(yi) = 1, 1 ≤ i ≤ 4. Thus, σ is a solution of Fif and only if it is a (1,0)-super solution of F ′. Therefore, (1,0)-4-SAT isNP-complete. Similar method can be used to reduce any k-SAT instance to(1, 0)-(k + 1)-SAT instance.2.2 Random models of k-SATWe denote by Fk(n,m) the standard random model for k-CNF formulason n variables where the m clauses are selected uniformly at random withoutreplacement from the set of all possible 2k(nk)k-clauses. As sometimes it ishard to directly analyse Fk(n,m) due to the dependence created by selectingthe clauses without replacement, we consider two related models. The firstmodel selects from all 2k(nk)proper clauses with replacement. The secondmodel selects each literal uniformly and independently with replacement.Both models may result in improper formula and the second model may haveimproper clauses. A clause is proper if it does not have repeated literals.A formula is proper if it does not have repeated clauses and each clause is72.3. The second moment methodproper. As long as k is fixed, the number of improper clauses and repeatedclauses is o(n) w.h.p. Therefore, with-high-probability properties of (1,0)-satisfiability hold in Fk(n,m) and two related models simultaneously. Fornotational convenience, we denote all three models by Fk(n,m). Also, whenthere is no ambiguity from the context, we use Fk(n,m) to denote a randomformula in the model Fk(n,m). When k ≤ 3, we use the first variant of themodel. When k ≥ 4, we use the second variant of the model. Throughoutthis chapter, we assume that k is fixed but can be arbitrarily large.Due to Lemma 2.2, for a fixed k-SAT F from Fk(n,m), the probabilityfor F to be (1,0)-satisfiable equals the probability for its projection T (F )to be satisfiable. This, however, does not imply that the probability for arandom formula in Fk(n,m) to be (1, 0)-satisfiable equals the probabilityfor a random formula in Fk−1(n, km) to be satisfiable. This is because for afixed (k−1)-SAT formula F of km clauses, the probability that F is selectedfrom Fk−1(n, km) is different from the probability that F is the projectionof some formula in Fk(n,m).2.3 The second moment methodThe probabilistic method, initiated by Paul Erdo¨s, is a powerful tool incombinatorics. Roughly speaking, in order to prove that an object with cer-tain properties exists, one constructs an appropriate probability space andshows that a randomly chosen object in this space has the desired propertieswith positive probability. Though the probabilistic method only proves theexistence of some object, there are techniques that help design algorithms tofind the satisfying objects [6]. If we can prove that the existence probabilitygoes to arbitrarily close to 1 when the size of the problem goes to infinity,we say that the object exists with high probability (w.h.p). The secondmoment method is a widely used tool to establish this type of results.In the context of this section, let X be a nonnegative integer-valuedrandom variable. Denote by E[X] the expectation of X, and V ar[X] thevariance of X, i.e., V ar[X] = E[(X − E[X])2]. For notational simplicity informulas, µ and σ2 are often used to replace E[X] and V ar[X]. We assumethat σ > 0 and call it the standard deviation. The second moment methodis based on the following two famous theorems.Theorem 2.4 (Markov’s Inequality, [6]). For any a > 0,P[X ≥ a] ≤ E[X]a82.3. The second moment methodTheorem 2.5 (Chebyshev’s Inequality, [6]). For any positive λ,P[|X − µ| ≥ λσ] ≤ 1λ2When X represents the number of desired objects, e.g. solutions of aproblem, we have P[X > 0] = P[X ≥ 1] ≤ E[X]. Therefore, in order to showthat X = 0 w.h.p., we prove that E[X] goes arbitrarily close to 0. On theother hand, in order to prove X > 0 w.h.p., we prove that P[X = 0] goesarbitrarily close to 0.Theorem 2.6. P[X = 0] ≤ V ar[X]E[X]2Proof. Substituting λ with µσ in the Chebyshev’s Inequality, we haveP[X = 0] ≤ P[|X − µ| ≥ λσ] ≤ 1λ2=σ2µ2In order to show X > 0 w.h.p. by the second moment method, there aretwo steps. First, prove that E[X] goes to infinity. Second, bound P[X = 0]with some infinitesimal. This can be done by showing that V ar[X] =o(E[X]2), according to Theorem 2.6. The relation V ar[X] = o(E[X]2) intu-itively means that E[X]2 = Θ(E[X2]). The following inequality is strongerthan the one in Theorem 2.6 and plays an essential role in our analysis.Lemma 2.7 (Exercise 3.6. [42] ). For any nonnegative integer-valued ran-dom variable X, if E[X] > 0, then P[X > 0] ≥ E[X]2E[X2].Proof. Let A be the set of positive values of X, i.e., A = {i|i > 0,P[X = i] >0}. ThenP[X > 0] · E[X2]=(∑i∈AP[X = i])·(∑i∈Ai2 · P[X = i])=∑i∈Ai2 · P[X = i] +∑i,j∈A,i 6=j(i2 + j2) · P[X = i] · P[X = j]≥∑i∈Ai2 · P[X = i] +∑i,j∈A,i 6=j(2 · i · j) · P[X = i] · P[X = j]=∑i∈A∑j∈Ai · j · P[X = i] · P[X = j]= E[X]2.92.4. The threshold for (1,0)-2-SATSince E[X2]> 0, we have P[X > 0] ≥ E[X]2E[X2].Another easy-to-use lemma is as follows.Lemma 2.8 (Corollary 4.3.5 of [6]). Let X =∑ni=1Xi, where Xi is theindicator random variable for event Ai. Denote by i ∼ j if i 6= j and theevents Ai, Aj are not independent. If limn→∞E[X] = ∞ and ∑j∼iP[Aj |Ai] =o(E[X]), then X > 0 holds w.h.p.2.4 The threshold for (1,0)-2-SATIn order to establish the threshold for a property, we must prove eventsdescribing that property occur w.h.p.Theorem 2.9. F2(n,m) is (1,0)-satisfiable w.h.p. when m = o(√n) and is(1,0)-unsatisfiable w.h.p. when m = ω(√n).Proof. We say that two clauses are conflicting if some literal in one clauseis the negation of some literal in the other clause. Note that a 2-CNFformula F is (1,0)-satisfiable if and only if no conflicting clauses exists. LetF = C1 ∧ · · · ∧ Cm and Xi,j be the indicator variable for the event that Ciconflicts with Cj . Then,E[Xi,j ] = P[Xi,j = 1] =2(2(n− 1)− 1) + 122(n2) =4n− 52n(n− 1) .Denote by X =∑(i,j)Xi,j the number of conflicting pairs in F , thenE[X] =(m2)E[Xi,j ] =m2n(1− o(1)).When m = o(√n), using Markov’s Inequality, we havelimn→∞P[X > 0] ≤ limn→∞E[X] = 0.Let t =(m2)and p = E[Xi,j ], then E[X] = tp. Note that, X2 is composedof t2 items of Xi,jXi′,j′ . Group these items according to h = |{i, j, i′, j′}|.We see that E[Xi,jXi′,j′]equals p when h = 2, and equals p2 otherwise.Thus, E[X2]= tp+ (t2 − t)p2. When m = ω(√n), using Lemma 2.7,limn→∞P[X > 0] ≥ limn→∞E[X]2E[X2]= limn→∞tptp+ 1− p = 1.102.5. The threshold for (1,0)-3-SAT2.5 The threshold for (1,0)-3-SATWe use the equivalence (Lemma 2.2) between a (1, 0)-super solution anda standard solution to study the threshold for the phase transition of (1, 0)-super solutions of random 3-SAT. Specifically, we upper bound (resp. lowerbound) the probability for F to be (1,0)-unsatisfiable by the probability ofsome necessary (resp. sufficient) condition on the unsatisfiability of its pro-jection T (F ) (a 2-CNF formula). The conditions we shall use are proposedin [11]. It is important to note that while T (F ) is a 2-CNF formula obtainedfrom a random 3-CNF formula F3(n,m), T (F ) itself is not distributed asthe random 2-CNF formula F2(n,m). This is the major obstacle we have todeal with in our analysis.Theorem 2.10. F3(n, rn) is (1,0)-satisfiable w.h.p. when r < 1/3 and is(1,0)-unsatisfiable w.h.p. when r > 1/3.The above result is proved in Lemma 2.12 and Lemma 2.14. In theproofs, we use F to denote a random formula F3(n, rn), m = rn, and writeN = 23(n3).2.5.1 Lower bound on the threshold for (1, 0)-3-SATA bicycle of length s, s ≥ 2, is a set of s+ 1 2-clauses C0, · · · , Cs over aset of s boolean variables x1, · · · , xs such that:1. C0 = (u ∨ l1) and Cs = (ls ∨ v),2. Ci = (li ∨ li+1), 0 < i < s,where li is either xi or xi, and u and v are from {xi, xi | 1 ≤ i ≤ s}. Thefollowing Lemma is proved in Theorem 3 of [11].Lemma 2.11. If a 2-CNF is unsatisfiable, then it contains a bicycle.Lemma 2.11 gives us a necessary condition of unsatisfiability of a 2-SAT.Using this necessary condition, we can upper bound the probability for a3-SAT to be (1,0)-unsatisfiable, and thus establish a lower bound of theprobability for a 3-SAT to be (1,0)-satisfiable.Lemma 2.12. F3(n, rn) is (1, 0)-satisfiable w.h.p. when r < 1/3.Proof. For any fixed bicycle B = C0 ∧ · · · ∧ Cs, we consider the number of3-CNF formulas that contain B in their projection. In order to count thisnumber, we must know the relationships between clauses in B. Specifically,112.5. The threshold for (1,0)-3-SATwe need to know whether two clauses could be siblings, i.e., being projectedfrom the same 3-clause in a 3-CNF formula. Let C = {C1, · · · , Cs−1}. It isclear that any pair of clauses in C must have 4 different literals. Thus, notwo clauses in C can be siblings. Similarly, no tuple of three clauses fromB can be siblings. However, (C0, Ci) can be siblings, and so are (Cs, Ci),0 ≤ i ≤ s. Let h be the number of pairs of clauses from B which are siblings.Denote by g(s, h) the number of 3-CNF formulas with m clauses that haveB in their projection. Let F be such a 3-CNF formula. F needs to select(s+1−h) 3-clauses so that T (F ) has B. Since B is fixed, h 3-clauses of these(s+ 1− h) 3-clauses are fixed and each clause of the remaining (s+ 1− 2h)clauses has two literals fixed. Thus, there are (2(n−2))s+1−2h choices of the(s+ 1− h) 3-clauses. The remaining m− (s+ 1− h) 3-clauses of F can beselected from (N − (s+ 1− h)) 3-clauses where N = 23(n3). Therefore,g(s, h) =(N − (s+ 1− h)m− (s+ 1− h))· (2(n− 2))s+1−2h.Let p(s) denote the probability that a fixed bicycle of length s is part ofT (F ). Then,p(s) ≤(Nm)−1(g(s, 0) + 2s · g(s, 1) + g(s, 2))≤(Nm)−12(s+ 1)(N − (s− 1)m− (s− 1))· (2(n− 2))s−3≤(3r2(n− 1))s−1· s+ 12(n− 2)2 .Let Ns denote the number of different bicycles of length of s and X be thenumber of bicycles in T (F ). It is clear that Ns < ns2s(2s)2. Therefore,E[X] =n∑s=2Nsp(s) ≤4n(n− 2)2n∑s=2s2(s+ 1)(3rnn− 1)s−1.When r < 1/3,limn→∞P[X > 0] ≤ limn→∞E[X] = 0.Thus, X = 0 w.h.p. It follows that F3(n, rn) is (1, 0)-satisfiable w.h.p.2.5.2 Upper bound on the threshold for (1, 0)-3-SATA snake of length t, t ≥ 1, is a conjunction of 2t 2-clausesC0 ∧ C1 ∧ · · · ∧ C2t−1122.5. The threshold for (1,0)-3-SATand has the following structure.1. Ci = (li ∨ li+1), 0 ≤ i ≤ 2t− 1. l0 = l2t = lt2. For any 0 < i, j < 2t− 1, li 6= lj and li 6= lj .The following Lemma is proved in Theorem 4 of [11].Lemma 2.13. If a 2-CNF contains a snake, then it is unsatisfiable.Lemma 2.13 gives us a sufficient condition of unsatisfiability of a 2-SAT.Using this sufficient condition, we can lower bound the probability for a3-SAT to be (1, 0)-unsatisfiable, and thus establish an upper bound on theprobability for a 3-SAT to be (1, 0)-satisfiable. Specifically, we show thatwhen r > 1/3, the projection of F3(k, rn) contains a snake of length log3r nw.h.p.Lemma 2.14. F3(n, rn) is (1, 0)-unsatisfiable w.h.p. when r > 1/3.Proof. Let A be a snake of length t, XA be the indicator variable for theevent that A occurs in F . Note that only the two pairs, (C0, Ct−1) and(Ct, C2t−1), can be siblings. Let s = 2t − 1 and let p(t) be the number ofoccurrences of a fixed snake of length t in T (F ). Then,p(s) =(Nm)−1(g(s, 0) + 2g(s, 1) + g(s, 2))≈(Nm)−14g(s, 2) ≈ ( 3r2n)s−11n2.Let X denote the number of snakes of length t in T (F ). Then,E[X] =(ns)s! 2sp(s) ≈ (3r)s/n.When r > 1/3 and t = ω(log3r n), limn→∞ E[X] =∞.In order to use the second moment method on X, we have to considercorrelations between snakes. To satisfy a clause (li ∨ lj), if li is true, then ljmust also be true. This implication can be represented by two arcs (li, lj),(lj , li) in a digraph. The digraph of a snake of length t is a directed cyclelt, l1, l2, · · · , ls, lt. It is clear that two snakes are not independent if and onlyif there are some common arcs in their directed cycles. Let B be another132.5. The threshold for (1,0)-3-SATsnake of length t. Suppose B shares i arcs with A and these arcs contain jvertices. Then,P[B|A] =(N−2t−(2t−i)m−2t−(2t−i))· (2(n− 2))2t · (2(n− 2))2t−i(N−2tm−2t)· (2(n− 2))2t≤(m− 2tN − 2t · 2(n− 2))2t−i≤(3r2n)2t−i.It is clear that those common i arcs comprise (j − i) directed paths. FixingA, there are L1 choices for the shared j vertices to occur in B, and thereare L2 choices for the remaining 2t− j vertices to occur in B.L1 =(2 ·(2t2(j − i)))2· (j − i)!≤ 4 · (2t)4(j−i)L2 ≤(n− j + 12t− j)(2t− j)! ·22t−j ≤ (2(n− j + 1))2t−jFor a given A, let A(i, j) be the set of snakes sharing i arcs and j verticeswith A, and writep(i, j) =∑B∈A(i,j)P[B|A] = L1L2P[B|A]≤(3r2n)2t−i4(2t)4(j−i) (2(n− j + 1))2t−j .If i ≤ t, then i+ 1 ≤ j ≤ 2i. If t < i ≤ 2t, then i+ 1 ≤ j ≤ 2t. Let A ∼ Bdenote the fact that A and B are dependent.∑A∼BP[B|A] =2t∑i=1min{2i,2t}∑j=i+1p(i, j) =2t∑j=2j−1∑i=j/2p(i, j)≤2t∑j=2(2(n− j + 1))2t−j 4j−1∑i=j/2(3r2n)2t−i(2t)4(j−i)≤2t∑j=2(2(n− j + 1))2t−j 4 · j2(3r2n)2t−j+1(2t)4≤2t∑j=22j(3r2n)(2t)4≤ Θ(1) · 1nt6 = o(1n(3r)2t)= o(E[X]).142.6. The threshold for (1,0)-k-SATAccording to lemma 2.8, limn→∞P[X > 0] = 1. Therefore, F is (1,0)-unsatisfiablew.h.p.2.6 The threshold for (1,0)-k-SATThe projection in Definition 2.1 provides a way to translate betweenan (1,0)-3-SAT instance and a 2-SAT instance. Because there are easy-to-use sufficient condition and necessary condition for 2-SAT, we can establishthe thresholds for (1,0)-2-SAT without looking into the distributions of its(1,0)-super solutions. However, for k > 3, we do not have such sufficientconditions and necessary conditions we had before. Therefore, we have tostudy the distributions of (1,0)-super solutions in order to get the thresholds.We start with upper bounds on the thresholds for (1,0)-k-SAT.Theorem 2.15. For all k ≥ 3, Fk(n, rn) is (1, 0)-unsatisfiable w.h.p. whenr > 2kk+1 ln 2.Proof. For a fixed assignment σ, a random k-clause is satisfied with proba-bility 1− 1+k2k . Denote by X = X(F ) the number of (1,0)-super solutions ofFk(n,m). ThenE[X] = 2n(1− 1 + k2k)rn =(2(1− 1 + k2k)r)n.When r > − ln 2ln(1− 1+k2k), by Markov’s Inequality, we havelimn→∞P[X ≥ 1] ≤ limn→∞E[X] = 0.Therefore, F is (1,0)-unsatisfiable w.h.p. Since 2kk+1 ln 2 >− ln 2ln(1− 1+k2k), thetheorem follows.In the rest of this section, we establish a lower bound on the thresholdfor k > 3 and show that the ratio of the lower bound over the upper boundgoes to 1 as k goes to infinity. Our analysis uses the techniques introducedin [4] for proving lower bounds on the threshold for the phase transition ofstandard satisfying solutions of random SAT, but the calculation we have todeal with is even more complicated. The idea is to use a weighting schemeon satisfying assignments when using the second moment method to provelower bounds on the threshold.152.6. The threshold for (1,0)-k-SATFor a clause c, denote by S(c) the set of (1, 0)-super solutions of c,S0(c) (resp. S1(c)) the set of assignments that satisfies exactly 0 (resp.1) literal of c. Define H(σ, c) to be the number of satisfied literals minusthe number of unsatisfied literals under an assignment σ. For an eventA, let 1A be its indicator variable. The weight of σ w.r.t. c is definedas w(σ, c) = γH(σ,c)1σ∈S(c), 0 < γ < 1 and is determined by k. Thesedefinitions extend naturally to a formula F ,w(σ, F ) = γH(σ,F )1σ∈S(F ) =∏ciw(σ, ci).Let X =∑σ w(σ, F ). It is clear that X > 0 if and only if F is (1,0)-satisfiable. We note that by viewing an instance of (1, 0)-k-SAT as a gener-alized Boolean satisfiability problem (Boolean CSP) and applying the condi-tions established in [14], random (1, 0)-k-SAT has a sharp threshold. There-fore, to show X > 0 w.h.p., it is sufficient to prove that P[X > 0] is largerthan some constant.For a fixed σ and a random k-clause c,E[w(σ, c)] = E[γH(σ,c)(1− 1σ∈S0(c) − 1σ∈S1(c))]=(γ + γ−12)k− 2−kγ−k − k2−kγ−k+2 = φ(γ).Thus, E[X] =∑σ∏ciE[w(σ, c)] = (2φ(γ)r)n.We now consider E[X2]. Fix a pair of assignments σ, τ such that theyoverlap each other on exactly z = αn variables. Consider a random k-clausec and writef(α) = E[w(σ, c)w(τ, c)] = E[γH(σ,c)+H(τ,c)1σ,τ∈S(c)].We have the following equations for relevant events1σ,τ∈S(c) = 1− 1σ 6∈S(c) − 1τ 6∈S(c) + 1σ,τ 6∈S(c),1σ 6∈S(c) = 1σ∈S0(c) + 1σ∈S1(c),1σ,τ 6∈S(c) = 1σ∈S0(c),τ∈S0(c) + 1σ∈S0(c),τ∈S1(c)+ 1σ∈S1(c),τ∈S0(c) + 1σ∈S1(c),τ∈S1(c).For mathematical expectations, we haveE[γH(σ,c)+H(τ,c)1]=(α(γ2 + γ−22) + 1− α)k,162.6. The threshold for (1,0)-k-SATE[γH(σ,c)+H(τ,c)1σ 6∈S(c)]= 2−k((αγ−2 + 1− α)k+k(αγ−2 + 1− α)k−1(αγ2 + 1− α)),E[γH(σ,c)+H(τ,c)1σ,τ 6∈S(c)]= 2−k(αkγ−2k + 2kγ−2k+2αk−1(1− α)+γ−2k+4(kαk + k(k − 1)αk−2(1− α)2)).Therefore, the expectation of X2 can be written asE[X2]=∑σ,τE[w(σ, F )w(τ, F )]=∑σ,τ∏ciE[w(σ, ci)w(τ, ci)] = 2nn∑z=0(nz)f(z/n)rn.The following lemma from [3] enables us to consider the dominant partof E[X2].Lemma 2.16. Let h be a real analytic positive function on [0, 1] and defineg(α) = h(α)/(αα(1− α)1−α), where 00 ≡ 1. If g has exactly one maximumat g(β), β ∈ (0, 1), and g′′(β) < 0, then there exists some constant C > 0such that for all sufficiently large n,∑nz=0(nz)h(z/n)n ≤ C × g(β)n.Let gr(α) = f(α)r/(αα(1−α)1−α). We say that gr(α) satisfies the dom-inant condition if gr ′′(1/2) < 0 and gr(1/2) is the unique global maximum.According to lemma 2.16 and φ(γ)2 = f(1/2), if gr(α) satisfies the dominantcondition, thenP[X > 0] >E[X]2E[X2]=4nf(1/2)rnE[X2]>(2gr(1/2))nC · (2gr(1/2))n=1C,where C is a constant when k is fixed.If we can find suitable γ and r so that gr(α) satisfies the dominant con-dition, then we can prove X > 0 w.h.p. Note that the dominant conditionimplies f ′(1/2) = 0. The weighting function w(σ, c) defined on an assign-ment σ and a k-clause c = (l1 ∧ · · · lk) can be viewed as defined on a vectorv in {−1, 1}k, where v(i) = −1 if li evaluates to False under σ and v(i) = 1172.6. The threshold for (1,0)-k-SATotherwise. According to [4], a necessary condition of f ′(1/2) = 0 is that thesum of vectors scaled by their corresponding weights is 0, i.e.,∑v∈{−1,1}kw(v)v = 0.Following the idea of [4], the γ which gives the best lower bound r shouldalso make weights of (1, 0)-satisfying assignments as equal as possible. Forour problem of (1, 0)-k-SAT, γ should satisfy the following equationk∑i=2(ki)γ2i−k(2i− k) = 0. (2.1)When k = 4, this equation requires γ = 0, which contradicts our prerequisitethat γ > 0. Thus, the weighting scheme is not meaningful when k = 4.Therefore, we consider k > 4 first and then solve the k = 4 case in adifferent way.It is too complicated to directly prove that gr(α) satisfies the dominantcondition, at least for small k. Therefore, we plot figures to show how gr(α)changes when k is fixed. Figure 2.1 shows the case when k = 5. Figuresshowing gr(α) of other fixed ks share the same changing pattern with thecase k = 5. For each k, when r is smaller than some r∗k, gr(α) satisfies thedominant condition and Fr(n, rn) is (1, 0)-satisfiable w.h.p. Thus r∗k is alower bound for Fk(n, rn) to be (1, 0)-satisfiable. We do this analysis for kup to 11 and show the values in Table 2.1. It is clear to observe that theratio of the lower bound over the upper bound of thresholds of Fk(n, rn)goes to 1 as k becomes large.We still have to solve the case k = 4 separately, where the weightingscheme, w(σ, c) = γH(σ,c)1σ∈S(c), does not work for any γ > 0. Since 2i− kis either 0 or positive when k = 4 and i ≥ 2, equation 2.1 cannot hold. Thus,a compromise is to consider only those assignments which satisfy 2i−k = 0.Specifically, for each clause of F , exactly two literals are satisfied and exactlytwo literals are unsatisfied. And every satisfying assignment has the sameweight, 1. By doing this, the likelihood for an assignment not to be in X isdoubled. Therefore, the upper bound for such solutions becomes 2k−11+k ln 2,half of the upper bound for (1, 0)-4-SAT. The remaining analysis of findingr∗k that satisfying the dominant condition is similar to the analysis of k > 4.The r∗4 we found is 0.602.182.7. Designing SAT benchmarks by projections0.20.30.40.50.60.70.80.91.01.10.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0Figure 2.1: k = 5, r = 1, 1.2, 1.6, 2, 2.4, 2.8, 3.2 (top down)Table 2.1: Upper bound and lower bound for (1, 0)-k-SATk 4 5 6 7 8 9 10 11upper bound 2.2 3.6 6.3 11.1 19.7 35.5 64.5 118.3lower bound 0.6 1.6 3.7 7.8 15.8 30.9 59.3 113.42.7 Designing SAT benchmarks by projectionsWe conducted preliminary experiments by using the uniform k-SAT gen-erator by Adrian Balint [5] and the SAT solver, MiniSAT [18], to solve 3-CNF formulas projected from random instances of (1, 0)-4-SAT on n = 500variables. The experiments were conducted on a 2.5GHz Intel Core i5 pro-cessor with 8GB memory. The time limit set for the solver are 600 seconds.Instances that cannot be solved within the time limit are treated as unsat-isfiable and a running time of 600 seconds is used in calculating the averagetime. The results of the solution probability and solution time (measuredin CPU seconds) are plotted in Figure 2.2, where each data point is theaverage of 100 randomly generated instances. As depicted in Figure 2.2, thephase transition of the (1, 0)-super solution is clear and the hardness peakat the phase transition seems to be as dramatic as (if not more dramaticthan) those of standard random 3-SAT instances.Our analysis of (1, 0)-super solutions in Sections 2.5 and 2.6 makes use ofthe observation that a random (1,0)-k-SAT instance can be projected to an192.7. Designing SAT benchmarks by projections020406080100120140160Average Time In Seconds (square point)0.00.20.40.60.81.0Frequency Of Solvability (circle point)1.2 1.3 1.4 1.5 1.6 1.7rFigure 2.2: Experimental results on (1,0)-super solutions of random 4-CNFformula, where r = m/n is the clause-to-variable ratio and n = 500.equivalent standard (k− 1)-SAT instance. While the projected (k− 1)-SATinstance is “random”, its distribution is different from the standard random(k − 1)-SAT instances, due to the correlations among the projected (k − 1)clauses. As our experiments shows, the projected (k − 1)-SAT “random”instances not only have a stylish easy-hard-easy hardness pattern, but alsoexhibit a seemingly more dramatic peak of harness at the phase transition.We note that the idea of projections and some of our analysis extend natu-rally to the case of (a, 0)-super solutions for a > 1. Given a random instanceF of (a, 0)-k-SAT with 1 < a < k, we can obtain a (k − a)-CNF formulaH by projecting the clauses of F recursively. It can be proved that F hasan (a, 0)-super solution if and only if H has a solution. Again, we notethat while F is a random k-CNF formula, the distribution of H differs fromthat of the standard random (k − a)-CNF formula; we expect to see thatclauses in H will have a unique clustering structure that does not exist in astandard random CNF formula. Therefore, projecting from random (a, 0)-k-SAT instances provides a promising approach to constructing new classesof random but structured SAT distributions. Our theoretical analysis andpreliminary experiments on the hardness of such instances suggest that thisclass of instances may serve as a suite of SAT benchmarks that interpolate202.8. Super solutions for random binary CSPsbetween randomness and structure in a unique way.2.8 Super solutions for random binary CSPsA well-studied random model of Constraint Satisfaction Problems (CSP)is the standard Model B in [24]. Phase transitions for the random binaryCSP under Model B is studied in [50]. In this section, we explore phasetransitions for the (1, 0)-super solution of random binary CSP under ModelB. Random binary CSPs are defined on a domain D of size |D| = d. Abinary CSP C consists of a set of variables X = {x1, · · · , xn} and a setof binary constraints (C1, · · · , Cm). Each constraint Ci is specified by itsconstraint scope, an unordered pair of two variables in X, and a constraintrelation RCi that defines a set of incompatible value tuples in the binaryrelation D ×D for the scope variables. An incompatible value tuple is alsocalled a restriction. The constraint graph of a binary CSP is a graph whosevertices correspond to the set of variables and edges correspond to the set ofconstraint scopes. We use the random CSP model Bd,qn,m defined as follows.1. Its constraint graph is a random graph G(n,m) where the m edges areselected uniformly at randomly from all the possible(n2)edges.2. For each edge, its constraint relation is determined by choosing eachvalue tuple in D × D as a restriction independently with probabilityq.Denote byH(σ1, σ2) the set of variables being assigned different values bytwo assignments σ1 and σ2, i.e., H(σ1, σ2) = {xi|σ1(xi) 6= σ2(xi), 1 ≤ i ≤ n}.Let σ be a fixed assignment and I be a random Bd,qn,m instance. Define thefollowing three events:1. S(σ) : σ is a solution for I.2. Si(σ) : there exists another solution σ′ for I such that H(σ, σ′) = {xi}.3. T (σ) : σ is a (1, 0)-super solution for I.According to the relationship between (1, 0)-super solutions and standardsolutions,P[T (σ)] = P[S(σ)]P[∩1≤i≤nSi(σ)|S(σ)].Estimating the probability of a (1, 0)-super solution for a random CSP in-stance is, however, more complicated than estimating the probability of a212.8. Super solutions for random binary CSPssatisfying assignment, largely due to the fact that the events Si(σ), 1 ≤ i ≤n, are not independent. This is the major hurdle we need to overcome.Note that in a random CSP instance, the selection of constraints andthe selection of restrictions for each constraint are independent. Let C ⊂(X × X)m be the collection of all possible sets of m unordered pairs ofvariables. For a given set e ∈ C of m unordered pairs, denote by E(e) theevent that e is selected as the set of constraints of the random instance I.Let mi be the number of constraints xi is involved with. Considering anassignment σ′, H(σ, σ′) = {xi}, it is clear thatP[S(σ′)|S(σ) ∩ E(e)]= 1− (1− q)mi .Let D′ = D \ {σ(xi)}, σ′(xi) = y, p = 1− q, thenP[Si(σ)|S(σ) ∩ E(e)] = P[∪y∈D′S(σ′)|S(σ) ∩ E(e))]= P[∩y∈D′S(σ′)|S(σ) ∩ E(e))]= 1− P[∩y∈D′S(σ′)|S(σ) ∩ E(e))]= 1− (1− (1− q)mi)d−1.This shows that, conditioned on S(σ) and a fixed set of constraints e, Si(σ)and Sj(σ) are independent for any i 6= j.P[T (σ)] = P[∪e∈C (E(e) ∩ S(σ) ∩ (∩1≤i≤nSi(σ)))]=∑e∈CP[E(e)]P[S(σ)|E(e)]P[∩1≤i≤nSi(σ)|S(σ) ∩ E(e)]=((n2)m)−1pm∑e∈Cn∏i=1(1− (1− pmi)d−1). (2.2)Let Yσ be an indicator variable of T (σ) and Y =∑σ Yσ be the numberof (1, 0)-super solutions. We haveE[Y ] = dn · E[Yσ] = dn · P[T (σ)]. (2.3)Theorem 2.17. Consider the random CSP Bd,qn,m with d =√n and m =c · n lnn where c is a positive constant. Let p = 1 − q. If c > −13 ln p , thenlimn→∞E[Y ] = 0 and thus, Bd,qn,m is (1, 0)-unsatisfiable w.h.p.222.8. Super solutions for random binary CSPsProof. Subject to∑ni=1mi = 2m, the product term on the right hand sideof Equation (2.2), achieves the global maximum when mi = 2mn , 1 ≤ i ≤ n.This can be proved by the method of Lagrange multipliers. Let c = c′ ·− 1ln p .According to Equation (2.2) and (2.3), we haveE[Y ] ≤ (d · pc lnn · (1− (1− p2c lnn)d−1))n= (d · nc ln p · (1− (1− n2c ln p)d−1))n≈ (n1/2−c′ · (1− (1− n−2c′)n1/2))n.For any a, b satisfying 0 ≤ a ≤ 1 and ab < 1, we have (1 − a)b ≥ 1 − ab. Ifc′ > 1/3, thenE[Y ] ≤ (n1/2−c′ · n−2c′n1/2)n = (n1−3c′)n.Therefore, limn→∞E[Y ] = 0.The case of c ≤ −13 ln p is even more difficult to analyse. In the following,we establish conditions for the expected number of (1, 0)-solutions, E[Y ],to go to infinity. Note that 1 − (1 − px)d is increasing in terms of x. Letλ = 2mn = 2c lnn and t = r lnn. If mi ≤ λ+ t for each 1 ≤ i ≤ n, thenE[Y ] > dnpm(1− (1− pλ+t)d−1)n≈ n(1+(3c+r) ln p)n.Consequently, when r < −1ln p − 3c, limn→∞E[Y ] = ∞. Therefore, for a fixedc < −13 ln p , if we could find an appropriate r such that mi ≤ λ+ t w.h.p., thenwe can prove limn→∞E[Y ] = ∞. Since dependencies among mis make it hardto analyse, we approximate them by the corresponding m′is in the randommodel where edges in the constraint graph are selected with replacement,in which case each m′i is a Binomial random variable with the distributionBin(m,n/2). By the Chernoff Bound for Binomial distributions, we havefor any u ≥ 0,P[mi ≥ λ+ t] ≤ P[m′i ≥ λ+ t]≤ e−u(λ+t)(1 + p(eu − 1))m.Therefore,P[∩1≤i≤nmi ≤ λ+ t] ≥ 1−∑1≤i≤nP[mi > λ+ t]≥ 1− nP[m1 > λ+ t]≈ 1− e(−u(2c+r)+(eu−1)2c+1) lnn.232.8. Super solutions for random binary CSPsConsequently, if1u+eu − 1u2c− 2c < r < −1ln p− 3c, r > 0, u ≥ 0,then w.h.p. mi ≤ λ + t, 1 ≤ i ≤ n, and thus E[Y ] goes to infinity. Sincec = c′ −1ln p and c′ < 13 , the parameter r has to satisfy−1ln p(1− c′(1 + 2(eu − 1)u)) >1u.By setting u = 1, we see that if c < − 110 1ln p and q = 1− p < 0.43, then theexpected number of (1, 0)-super solutions E[Y ] goes to infinity.Note that what we get in the above passage is just a coarse lowerbound on the thresholds for the (1, 0)-satisfiability of a random instanceof Bd,qn,m. This is because limn→∞ E[X] is only a necessary condition forlimn→∞ P[X > 0] = 1. In order to prove that there is a (1, 0)-super so-lution, we must use the second moment method to prove Lemma 2.8 orsome other weaker version of it. Also note the significant gap between thelower bound and the upper bound we have derived in Theorem 2.17 and theabove analysis. This indicates that analysing the threshold phenomena of(1, 0)-super solutions for random CSPs is a much more challenging task andrequires new analytical ideas.24Chapter 3Partitioning of graphs intocographs3.1 Graphs and graph colouringWe first introduce some definitions and notations for graphs [7]. A graphG is an ordered pair, (V (G), E(G)), often written as G(V,E) where V (G) isa set of vertices and E(G) is a set of unordered pair of vertices. The orderof a graph is the number of its vertices. An unordered pair {u, v} ∈ E(G)is called an edge of G and is often written as uv. For an edge e = uv, u andv are called ends of e and u is said to be adjacent to v. Two vertices u andv in G are called non-adjacent if uv 6∈ E(G). Ends of an edge are said tobe incident with the edge, and vice versa. Two edges are adjacent if theyshare an end and are non-adjacent otherwise. A set of pairwise non-adjacentedges in a graph is called a matching. The neighbourhood of a vertex v in agraph G, denoted by NG(v), is the set of vertices that are adjacent to v inG. When G is clear from the context, we simplify the notation as N(v).A loop is an edge with identical ends (e.g. for some vertex u, {u, u} isan edge). Two or more edges with the same ends are called parallel edges.A graph is simple if it has no loops or parallel edges. In the context of thisthesis, we consider simple graphs only. A vertex v is isolated in a simplegraph G if NG(v) = ∅. A path is a simple graph whose vertices can bearranged into a linear sequence such that ends of each edge are consecutivein the sequence. Paths with k vertices are written as Pk. Two vertices ina graph G are connected if there is a path between them in G. A graph isconnected if every two vertices are connected and disconnected otherwise. Acycle with k vertices, denoted by Ck, is a simple graph whose vertices canbe arranged in a cyclic sequence such that ends of each edge are consecutivein the sequence. Cycles in simple graphs require at least three vertices. Thelength of a path or a cycle is the number of its edges. A path or cycle is odd(resp. even) if its length is odd (resp. even). An empty graph is graph inwhich no two vertices are adjacent and a complete graph is a simple graph253.1. Graphs and graph colouringin which every pair of vertices is adjacent. A complete graph with n verticesis denoted by Kn.The complement of a graph G, denoted G, is a graph whose vertex setis V (G) and whose edges are the pairs of non-adjacent vertices of G. Twographs are disjoint if they have no vertex in common. The union of simplegraphs G and H is the graph G∪H with vertex set V (G)∪ V (H) and edgeset E(G) ∪ E(H). If G and H are disjoint, we refer to their union as adisjoint union and denote it by G + H. A graph G is disconnected if andonly if G is a disjoint union of some connected subgraphs and each suchsubgraph is called a connected component of G. Given two disjoint graphsG and H, the join of G and H, denoted by G⊕H, is a graph with the vertexset V (G+H) and the edge set E(G+H) ∪ {uv|u ∈ V (G), v ∈ V (H)}.A graph F is called a subgraph of a graph G if V (F ) ⊆ V (G) andE(F ) ⊆ E(G). If F is a subgraph of G, then G contains F . A subgraph F ofa graph G is called a proper subgraph of G if V (F ) ⊂ V (G) or E(F ) ⊂ E(G).For an edge e ∈ E(G), the edge-deletion subgraph, G− e, is the graph withthe same vertex set as G but whose edge set is E(G) \ {e}. For a vertexv ∈ V (G), the vertex-deletion subgraph, G− v, is the graph with the vertexset V (G)\{v} and the edge set E(G)\{e|e is incident with v}. A subgraphobtained by vertex deletions only is called an induced subgraph. If X is aset of vertex deletions, the resulting subgraph is denoted by G−X or G[Y ]where Y = V \X. G[Y ] is also known as the subgraph of G induced by Y .For a graph G and a nonempty set of vertices U ⊆ V (G), U is a stable set ofG if G[U ] is empty and U is a clique of G if G[U ] is complete. A partition ofa set V is a set of nonempty subsets of V such that each element of V is inexactly one of the subsets. The order of a partition is the number of subsetsin the partition. A bipartition is a partition of order two. A partition of agraph G is the set of subgraphs induced by all subsets of some partition ofV (G).Two graphs G and H are isomorphic, written as G ∼= H, if there existsa bijection θ : V (G) → V (H) such that for every two vertices u, v ∈ V (G),uv ∈ E(G) if and only if θ(u)θ(v) ∈ E(H). A graph G is called H-free ifthere is no induced subgraph of G which is isomorphic to H.A colouring of a graph G is a function f : V (G)→ S where S is a finiteset. The elements of S are called labels or colours. The vertices that mapto the same colour form a colour class. A colouring is called a k-colouring ifS has size k. For a graph G and two subsets U and U ′ of V (G), U ⊂ U ′, toextend a colouring σ of G[U ] to G[U ′] is to exhibit a colouring σ′ of G[U ′]such that σ(v) = σ′(v) for all v ∈ U .A colouring is H-free if the subgraph induced by each colour class is H-263.2. Cographs and the cog-chromatic numberfree. An H-free colouring of a graph is equivalent to a partition of the graphinto H-free graphs. A graph is H-free k-colourable if it admits an H-free k-colouring. The minimum k for which a graph is H-free k-colourable is calledits H-free chromatic number. Following the commonly used terminology, thechromatic number of a graph G, written as χ(G), is the K2-free chromaticnumber of G and a graph is k-colourable means it is K2-free k-colourable.The following theorem is conjectured in [8] and proved in [1].Theorem 3.1. Deciding whether a graph admits a G-free k-colouring isNP-complete for any fixed G with at least 3 vertices and k ≥ 2.3.2 Cographs and the cog-chromatic numberThe set of all cographs (complement reducible graph) is defined recur-sively using the following rules:1. A single vertex (K1) is a cograph.2. The disjoint union of two cographs is a cograph.3. The complement of a cograph is a cograph.Cographs form the minimal family of graphs containing K1 and are closedunder complementation and disjoint union. Cographs have arisen in manydisparate areas and rediscovered under different names by different researchers[40]. A well-known characterization of cographs is that cographs are exactlythe P4-free graphs [51]. The process of deciding whether a graph G is in aset of graphs G is called recognizing G. There are many algorithms [13, 29]which recognize cographs in linear time.Here we will study partitioning graphs into cographs, i.e., P4-free colour-ing of graphs. We call a P4-free colouring a cog-colouring and the P4-freechromatic number as the cog-chromatic number, denoted by c(G). For ex-ample, cographs have cog-chromatic number 1 and P4 has cog-chromaticnumber 2. The cog-chromatic number is studied in [25, 46]1. A graph G isk-cog-colourable if c(G) ≤ k and is k-cog-chromatic if c(G) = k.In order to study this relatively new graph parameter, c(G), we startwith a study of graphs G with c(G) ≤ 2. These graphs have been called P4-bipartite in the literature [35]. Following the notation of graph editing [9],we define cograph+kv to be the set of graphs that have an induced cographsubgraph obtained by deleting at most k vertices. When k = 1, we omit the1The cog-chromatic number is called the c-chromatic number in [25]273.2. Cographs and the cog-chromatic numberk and denote the set as cograph+v. For notational convenience, we call agraph G cograph+kv if G is contained in the set cograph+kv.Weakly chordal graphs (or weakly triangulated graphs) are defined fork ≥ 5 as Ck-free graphs in [32]. Since cographs are P4-free, all graphs incograph+v must be C5-free. Thus, we have the following remark.Remark 3.2. cograph+v graphs are weakly chordal.Remark 3.3. cograph+v graphs can be recognized in linear time.Proof. Run a linear recognition algorithm for cographs on a graph G. If G isa cograph, we recognize G as cograph+v in linear time. If G is not a cograph,the algorithm will output an induced P4, say v1v2v3v4. Then, for each viin this P4, we run the algorithm on G − vi. If some run recognizes G − vias a cograph, then we recognize G as cograph+v in linear time. Otherwise,none of these four runs recognizes G − vi as a cograph. In this case, if uis not a vertex from {v1, v2, v3, v4}, then G− u will contain v1v2v3v4, a P4.Therefore, G is recognized as not being cograph+v in linear time.Since cograph+v graphs can be recognized in linear time and cographsare the P4-free graphs, cograph+v might be characterized by a finite set offorbidden subgraphs. That is, there may be a finite collection of graphs, C,such that a graph is cograph+v if and only if it is G-free for every graphG ∈ C. We call a graph non-cograph+v if it is not cograph+v. A graph G isvertex-minimal with respect to a graph class G if G ∈ G and G− v 6∈ G forevery v ∈ V (G). According to the definition of forbidden subgraph charac-terizations, C must include all vertex-minimal non-cograph+v graphs. Ob-serve that the complement of a cograph+v graph is still a cograph+v graphand the complement of a non-cograph+v graph is still a non-cograph+vgraph. Thus, a graph is a vertex-minimal non-cograph+v graph if and onlyif its complement is a vertex-minimal non-cograph+v graph. Therefore, Cis self-complementary, i.e., if G ∈ C, then G ∈ C. Some graphs in theC are C5, C6, C7, C8, P8 and their complements. However, this list is notcomplete and we have been unable to characterize cograph+v in a nice oruniform way. For example, the graph in Figure 3.1 is a vertex-minimal non-cograph+v graph but it is hard to come up with a unifying description ofthe characterization.Remark 3.2 and Remark 3.3 imply that cograph+v graphs are easy torecognize and many problems can be solved efficiently on them. However,problems related with cograph+kv graphs seem hard to attack as madeprecise in the following remark.283.2. Cographs and the cog-chromatic numberFigure 3.1: A vertex-minimal non-cograph+v graphRemark 3.4 ([55]). Deciding whether a graph is cograph+kv, where k is aninput parameter, is NP-complete.P4-bipartite graphs have intersections with many other graph classes.Intuitively, for a graph G, the more complex the way of vertices of G forminduced P4s is, the harder it is to compute c(G). The P4-structure of agraph G is the collection of subsets of size 4 of V (G) such that the subgraphinduced by each subset is a P4 in G. Two graphs G and H are P4-isomorphicif there exists a bijection θ : V (G) → V (H) such that for any four vertices{u1, u2, u3, u4} ⊆ V (G), u1u2u3u4 is an induced P4 of G if and only ifθ(u1)θ(u2)θ(u3)θ(u4) is an induced P4 of H. Two graphs which are notisomorphic may be P4-isomorphic (e.g. a triangle and a P3). P4-isomorphicgraphs have the same cog-chromatic number. An interesting result in [33]shows that, given a collection of subsets of four vertices, H, it is polynomiallysolvable to decide whether H is equivalent to the P4-structure of some graphG.We now explore relationships between P4-bipartite graphs and othercommonly known graph classes. A graph is P4-sparse if every subgraphinduced by five vertices contains at most one P4. P4-sparse graphs areshown to to be P4-bipartite in [35]. A graph is split if it can be partitionedinto a stable set and a clique. A graph is split-perfect if and only if it isP4-isomorphic to a split graph. Since stable sets and cliques are cographs,split graphs and split-perfect graphs are P4-bipartite.Remark 3.5. P4-sparse graphs and split-perfect graphs are subclasses of P4-bipartite graphs.As for a superclass of 2-cog-colourable graphs, we have not found a well-known graph class other than the trivial class of k-cog-colourable graphs,k ≥ 3.Unlike cographs which are easy to recognize and for which many prob-lems admit efficient algorithms, Theorem 3.1 shows that it is NP-hard todetermine whether a graph is P4-bipartite. Also, many problems on P4-bipartite graphs are shown to be NP-complete, such as Maximum Clique[47] and Hamiltonian Cycle [43]. In the following, we prove that k-colourability is NP-complete for P4-bipartite graphs.293.2. Cographs and the cog-chromatic numberT FBx1 x1x2 x2xn xnC11C21 C31 C41C51 C61x1x2x3T Flause gadget for a lause (x1 ∨ x2 ∨ x3)true-false gadgetFigure 3.2: Reduction from 3-SAT to χ(G) = 3Theorem 3.6. Let G be an arbitrary P4-bipartite graph. Deciding whetherχ(G) = 3 is NP-complete.Proof. For an arbitrary graph G, deciding χ(G) = 3 is proved to be NP-complete in Theorem 8.22 of [38]. The proof there reduces solvability of3-SAT to 3-colourability of graphs. We show that their reduction from 3-SAT is always P4-bipartite.We describe the reduction here briefly and describe a bipartition ofthe graph into cographs. Given an instance of 3-SAT with n variables{x1, · · · , xn} and m clauses {C1, · · · , Cm}, a graph with 2n+ 6m+ 3 verticesis created. There are 2n vertices that correspond to the 2n literals. For eachclause, six vertices are added. There are three special nodes, “T”, “B”, “F”that indicate three colours. Figure 3.2 shows the two types of gadgets. Thetrue-false gadget on the left side forces each vertex that corresponds to someliteral to choose colour either “T” or “F” in any 3-colouring. For each clauseCi, add six vertices C1i , · · · , C6i and connect them to vertices in the way ofthe clause-gadget. In the clause-gadget, any 3-colouring must assign colour“T” to at least one of the three vertices correspond to the three literals.Thus, clause Ci is satisfied if and only if the clause-gadget is 3-colourable.Now we prove that G can be partitioned into 2 cographs. Let A1 ={T,B, F} ∪ {xi, xi|1 ≤ i ≤ n} ∪ {C1i |1 ≤ i ≤ m} and A2 = {Cji |1 ≤ i ≤m, 2 ≤ j ≤ 6}. For any four vertices U in A1, G[U ] is either disconnectedor G[U ] has a triangle. Thus, G[A1] is a cograph. G[A2] is a set of disjointedges and hence is also a cograph. Therefore, {A1, A2} is a bipartition of Ginto two cographs.303.3. Approximating the cog-chromatic numberLet G be an arbitrary P4-bipartite graph and u be a vertex not in V (G).Since the join of two cographs is a cograph, we have c(G⊕ {u}) = c(G). Inany K2-free colouring σ of G ⊕ {u}, σ(u) 6= σ(v) for any v ∈ V (G). Thusχ(G ⊕ {u}) = χ(G) + 1. Therefore, we can reduce the problem of decidingχ(G) = k for P4-bipartite graphs to problem of deciding χ(G) = k + 1 forP4-bipartite graphs, in polynomial time.Corollary 3.7. Let G be an arbitrary P4-bipartite graph. Deciding whetherχ(G) = k is NP-complete for any fixed k ≥ 3.3.3 Approximating the cog-chromatic numberAs it is NP-hard to find a best cog-colouring for graphs, we turn now tofinding approximation algorithms that output near-optimum cog-colourings.The study of approximating the chromatic number, χ(G), plays a very im-portant role in both graph theory and computational complexity theory.The study gives rise to the famous theorem of “Probabilistically CheckableProof (PCP)” (see Chapter 17 of [28]). The PCP theorem is the cornerstoneof the theory of computational hardness of approximation and gives a finerclassification of problems in NP. In this section, we approximate c(G) forP4-bipartite graphs G.3.3.1 Greedy colouringIn the study of the classic graph colouring, greedy colouring using anorder of the vertices is studied. Suppose colours are represented by consecu-tive positive integers. The algorithm colours vertices according to the givenorder and greedily gives the next vertex u the smallest possible colour thathas not been used by vertices which are adjacent to u and precede u in theorder. It is reasonable to consider how well this greedy strategy works for ap-proximating the cog-chromatic number of a graph. We give the next vertexin the order the smallest colour such that subgraph induced by each colourclass (defined up to this iteration of the algorithm) is a cograph. Since anysimple graph G with less than four vertices is a cograph, c(G) ≤ dn3 e, wheren = |V (G)|. We construct a P4-bipartite graph below and describe an orderthat makes the greedy colouring algorithm use n/3 colours. This impliesthat greedy cog-colouring strategy is not a good idea for approximating thecog-chromatic number.For k ≥ 2, and 0 ≤ i < k, let v3iv3i+1v3i+2 be a P3. Join each vertex of{v3i, v3i+1, v3i+2} to each vertex of {v3j+2|j < i}. Let the resulting graph be313.3. Approximating the cog-chromatic numberFigure 3.3: Worst case example of greedy P4-free colouringGk. Figure 3.3 shows a construction where we label the vertices with theirindices. First, observe that v0v1v2v3 is a P4 in each Gk and hence c(Gk) ≥ 2.Moreover, note that the subgraph induced by {v3i+2|i < k} is complete andhence a cograph, and the subgraph induced by {v3i, v3i+1|i < k} is a set ofdisjoint edges and hence is also a cograph. Therefore, c(Gk) = 2.Remark 3.8. Given Gk and an order of V (Gk) that arranges vertices in anincreasing order of their indices. Let Ck = {c0, c1, · · · , ck−1} be a set of kcolours. For any k ≥ 1 and 0 ≤ i < k, the greedy cog-colouring coloursvertices of {v3i, v3i+1, v3i+2} with ci.Proof. We prove by induction on k.Base Step (k = 1): Since the graph induced by {v0, v1, v2} is a cograph,they are coloured c0.Inductive Step: Suppose for some k ≥ 1, the statement of the remarkis true for all Gj , j ≤ k. Consider Gk+1. Let u be any vertex from{v3k, v3k+1, v3k+2}. For any i, 0 ≤ i < k, since the subgraph induced by{v3i, v3i+1, v3i+2, u} is a P4 and each vertex of {v3i, v3i+1, v3i+2} is, by in-duction, coloured ci, u cannot be coloured ci. Thus, the vertices of {v3k,v3k+1, v3k+2} are coloured ck and the statement of the remark is true forGk+1.Remark 3.8 implies that the greedy cog-colouring outputs a k-cog-colouringof Gk if the given order is an increasing order of the indices of vertices. SinceGk has 3k vertices and is P4-bipartite, the greedy cog-colouring strategy isnot a good algorithm for approximating the cog-chromatic number.323.3. Approximating the cog-chromatic number3.3.2 Maximum induced cographIn any bipartition of a P4-bipartite graph with n vertices, the larger partmust have at least n/2 vertices. Thus, if we could find a maximum inducedcograph from a P4-bipartite graph G, then we can partition G into at mostlog2 n cographs where n = |V (G)|. This is because the number of remainingvertices decreases by at least half, after giving a maximum cograph a newcolour. In the following, we study the complexity of finding a maximuminduced cograph from P4-bipartite graphs.A graph G is bipartite if there is a bipartition {X,Y } of G, written asG[X,Y ], such that both G[X] and G[Y ] are stable sets. A bipartite graphG[X,Y ] is complete bipartite if every vertex in X is connected to every vertexin Y . A complete bipartite graph is also known as a biclique. A graph isbipartite if and only if it does not contain any odd cycle [7].Lemma 3.9. A connected cograph G is K3-free if and only if G is a biclique.Proof. “Only If”: If G is not bipartite, then the smallest odd cycle of G haslength larger than or equal to 5, contradicting the assumption that G is acograph. Let [X,Y ] be any bipartition of G such that X and Y are stablesets. Suppose G is not a biclique. Then there exists a pair of vertices u andv, u ∈ X, v ∈ Y , but uv 6∈ E(G). Let P be the shortest path from u to v ande = uv. Since G is a connected cograph, P has length of 2, contradictingthe assumption that G[X,Y ] is bipartite. Therefore, if a connected cographG is K3-free, then G is a biclique.“If”: For any biclique G, the length of the shortest path between anytwo vertices of G is either 1 or 2. Therefore, G does not contain an inducedP4 in G and G is a connected cograph.Finding a biclique with the most number of vertices in a bipartite graphis polynomially solvable as shown in [31]. According to Lemma 3.9, a bipar-tite graph is a cograph if and only if it is a bicluster, i.e., a disjoint union ofbicliques. Therefore, a cograph with the most number of vertices in a bipar-tite graph G is a set of maximum bicliques from the connected componentsof G.Corollary 3.10. Finding a maximum induced cograph is polynomially solv-able for bipartite graphs.A stable set U of G is maximum if there is no stable set U ′ of G suchthat |U ′| > |U |. Given a graph G and a positive integer k, the Stable Setproblem asks whether G has a stable set of size k. The Stable Set problem333.3. Approximating the cog-chromatic numberv1 v2v3v′1 v′2v′3G G′Figure 3.4: Reduction from Stable Set to Cograph problemis one of Karp’s 21 NP-complete problems [36]. The following hardness resultis implied by a theorem in [55]. The proof given in [55] is for a much moregeneral result and is very involved. We prove it for our specific case in asimpler way.Lemma 3.11. Finding a maximum induced cograph is NP-hard for generalgraphs.Proof. We prove that deciding whether a graph has a cograph of size k (theCograph problem) is NP-complete, via a reduction from the Stable Setproblem. It takes linear time to check whether a subgraph induced by kvertices is a cograph [29]. Thus, the Cograph problem is in NP. Givena graph G with n vertices, we create a new graph G′ with 5n vertices asfollowing. Let G′ be a copy of G. For each v ∈ V (G), denote by v′ thecorresponding vertex of v in G′. For each vertex of v ∈ V (G), create a joinbetween v′ and a disjoint copy of P4. Figure 3.4 shows an example of thisconstruction on a triangle. We claim that G has a stable set of size k if andonly if G′ has a cograph of size 3n + k. Denote by P4(v′) the P4 joined tov′.“Only If”: Suppose U ⊆ V (G) is a stable set of G with k vertices, letA = {v′|v ∈ U} ∪ { three vertices which form a P3 in P4(v′)|v ∈ V (G)}.Each component of G′[A] is a join between K1 and P3. Thus, G′[A] is acograph with 3n+ k vertices.“If”: Suppose the subgraph induced by U ⊆ V (G′) is a cograph of size3n+ k. Let U = U1 ∪U2, where U1 is a subset of vertices which correspondto vertices of G and U2 is the subset of vertices from added P4s. We performa case analysis according to |U1|.Case 1: |U1| = k.Since |U2| = 3n and G′[U2] is a cograph, U2 has exactly 3 vertices fromeach added P4. If U1 is not a stable set, then there is a P4, v1v2v3v4 in343.3. Approximating the cog-chromatic numberG′, where v2v3 is an edge in G′[U1], v1 and v4 are vertices in P4(v2) andP4(v3) respectively, contradicting the assumption that G′[U ] is a cograph.Therefore, {v|v′ ∈ U1} is a stable set of G with size k.Case 2: |U1| > k.Since |U2| < 3n, there is a vertex v′ that |U2 ∩ P4(v′)| = l, l ≤ 2. Thefollowing vertex exchange operation of adding vertices to U2 and removingvertices from U1 reduces the size of U1 by one while preserves the propertiesthat |U | = 3n + k and G′[U ] is a cograph. When v′ ∈ U1, the exchangeadds 3 − l vertices from P4(v′) to U2 and removes v′ and other arbitrary2 − l vertices from U1. When v′ 6∈ U1, the exchange adds 3 − l verticesfrom P4(v′) to U2 and removes other arbitrary 3− l vertices from U1. After|U1| − k vertex change operations, |U1| = k and we are in case 1.Lemma 3.11 shows the complexity of the maximum induced cographproblem for general graphs. Note that there are many graphs which are notP4-bipartite. We have the following conjecture.Conjecture 3.12. Finding a maximum induced cograph is NP-hard for P4-bipartite graphs.3.3.3 Approximation algorithmsThe degree of a vertex v in a simple graph G, denote by dG(v), is thesize of its neighbourhood NG(v). Denote by ∆(G) the maximum degree ofvertices of G. When G is clear from the context, we simplify notations ofdG(v) and ∆(G) as d(v) and ∆ respectively. A P3-free colouring is triviallya P4-free colouring. Denote by p3(G) the P3-free chromatic number of agraph G. The proof technique in the following remark has been used manytimes [19, 25].Remark 3.13. For any graph G, p3(G) ≤⌈∆+12⌉.Proof. Consider a colouring σ of G using k =⌈∆+12⌉colours that minimizesthe number of monochromatic edges. We claim that σ is a P3-free colouring.Suppose there is a monochromatic P3, v1uv2, that is coloured all red. SincedG(u) < 2k, there is at least one other colour, say blue, which is used atmost once by vertices which are adjacent to u. Switch u’s colour from redto blue and keep colouring of other vertices unchanged. After switching u’scolour, we decrease the number of monochromatic edges by at least one, con-tradicting the assumption that σ minimizes the number of monochromaticedges.353.4. Minimum order of k-cog-chromatic graphsAlgorithm 1 is an implementation of the proof of Remark 3.13. Letn = |V (G)| and m = |E(G)|. Lines from 3 to 4 are executed at most mtimes since each iteration decreases the number of monochromatic edges.Line 3 checks at most ∆ vertices for each colour and line 2 needs O(n3) timeto enumerate all P3s if G is represented by an adjacency matrix. Thus, thealgorithm finds a P3-free colouring of a graph in O(mn3∆2) time.Algorithm 1 Partitioning G into P3-free graphs1: Arbitrarily colour G using k =⌈∆+12⌉colours2: while There is a monochromatic P3, say v1uv2 do3: Find a colour x used by at most one vertex in u’s neighborhood4: Let x be the new colour of uTheorem 3.14. A P4-bipartite graph with maximum degree ∆ can be par-titioned into⌈∆+12⌉cographs in polynomial time.A hypergraph is an ordered pair (V,F), where V is a set of vertices andF is a family of subsets of V . Each subset in F is called a hyperedge or anedge of the hypergraph. A hypergraph is k-uniform if each of its hyperedgeshas k vertices. A proper colouring of a hypergraph is a colouring of V suchthat there is no monochromatic hyperedge. A hypergraph is k-colourable ifit admits a proper colouring which uses k colours. Thus, a cog-colouring of agraph G(V,E) into cographs is a proper colouring of a 4-uniform hypergraphH(V,F), where the subgraph induced by each hyperedge of F is a P4 in G. Gis P4-bipartite if and only if H is 2-colourable. A polynomial algorithm thatcolours a 2-colourable hypergraph using O(n3/4 log34 n) colours is describedin [37], where n is the number of vertices. Thus, a P4-bipartite graph with nvertices can be partitioned into O(n3/4 log34 n) cographs in polynomial time.3.4 Minimum order of k-cog-chromatic graphsIn this section, we study the minimum number of vertices a k-cog-chromatic graphs must have. The following way of constructing a (k + 1)-cog-chromatic graph from a k-cog-chromatic graph is given in [25].Definition 3.15 (3+1 construction). Given a graph G, let G1, G2, G3 bethree disjoint copies of G. The 3 + 1 construction T (G) from G is the unionof G1 ⊕G2, G2 ⊕G3 and G3 ⊕K1.363.4. Minimum order of k-cog-chromatic graphsLemma 3.16 (Remark 9 in [25]). c(T (G)) = c(G) + 1.Proof. Let T (G) = (G1⊕G2)∪ (G2⊕G3)∪ (G3⊕{x}), where x correspondsto the vertex of K1 in the definition of the 3+1 construction. Let k = c(G)and Cl = {c1, · · · , cl} be a set of l colours for any l ≥ 1. We categorize theinduced P4s contained in T (G) into two types.1. Type-1 P4: The four vertices are contained in Gi, for some 1 ≤ i ≤ 3.2. Type-2 P4: The P4 is u1u2u3x, where ui ∈ V (Gi) for 1 ≤ i ≤ 3.Note that there are no other types of P4s in T (G) since the subgraph inducedby any set of four vertices of T (G) that includes at least two vertices fromone Gi and a vertex not in Gi either contains a triangle or is disconnected.We first prove that c(T (G)) ≤ k + 1. Let σ be a k-colouring which cog-colours G1, G2 and G3 using colours from Ck. Extend σ to colour x withck+1. Neither a Type-1 P4 nor a Type-2 P4 is monochromatic under σ.Thus, σ is a (k + 1)-cog-colouring of T (G).We now prove that c(T (G)) > k. Suppose there is a k-cog-colouringσ of T (G) using colours from Ck. For each 1 ≤ i ≤ 3, since c(Gi) = k,the colour σ(x) must be used by some vertex ui of Gi. Thus, u1u2u3xis a monochromatic induced P4, contradicting the assumption that σ is acog-colouring of T (G).Therefore, c(T (G)) = k + 1.Let P be a graph property. A graph G is minimal with respect to P ifG has property P and if any proper subgraph of G does not have propertyP. G is minimum with respect to P if G has property P and if any graphG′ with less than |V (G)| vertices does not have property P.Let fc(k) be the order of the minimum k-cog-chromatic graphs. It is clearthat fc(1) = 1 and fc(2) = 4, because any graph with at most 3 vertices isa cograph and P4 is 2-cog-chromatic. Figure 3.5 shows a graph J with 10vertices that is 3-cog-chromatic (this graph comes from [25]). The authorsconjecture that J is a minimum 3-cog-chromatic graph. That is, fc(3) ≤ 10.In order to check whether fc(3) = 10, we use “geng”, a computer tool,described in [41], to generate all possible graphs of 9 vertices. Indeed, everygraph with 9 vertices can be partitioned into 2 cographs. Thus, we confirmthat fc(3) = 10. Starting with graph J in Figure 3.5, for any k > 3, oneobtains a k-cog-chromatic graph after k − 3 iterations of applying the 3+1construction to the resulting graph of the previous iteration. The resultinggraph has(10 · 3k−3 + (3k−3 − 1)/2)vertices. Thus, fc(k) = O(3k).373.4. Minimum order of k-cog-chromatic graphsFigure 3.5: A graph J of c(J) = 3 with 10 verticesThe construction in the following lemma uses fewer vertices than the oneof the 3+1 construction in Lemma 3.16.Lemma 3.17. Let G1, G2, G3, G4 be four disjoint graphs, H be the unionof G1 ⊕ G2, G2 ⊕ G3 and G3 ⊕ G4. For k ≥ 1, if c(G1) = c(G4) = k andc(G2) + c(G3) = k + 1, then c(H) = k + 1.Proof. Let Cl = {c1, · · · , cl} be a set of l colours for any l ≥ 1.First, we prove that c(H) ≤ k + 1. Let σ be a cog-colouring of G1and G4 using colours from Ck. We extend σ to cog-colour G2 using colours{c1, · · · , cx} where x = c(G2) and to cog-colour G3 using colours {cx+1, · · · ,ck+1}. The only possible induced P4 whose vertices might be given thesame colour must have one vertex from G1, G2, G3 and G4 respectively.However, such a path cannot be monochromatic because vertices in G2 andG3 do not have a common colour. Therefore, σ is a cog-colouring of H andc(H) = k + 1.Second, we prove that c(H) > k. Suppose there is a k-cog-colouringσ of H using colours from Ck. Since c(G2) + c(G3) > k, the Pigeon-HolePrinciple guarantees some colour ci must be used by some vertex from V (G2)and some vertex from V (G3). Since c(G1) = c(G4) = k, ci must also be usedby some vertex from V (G1) and some vertex from V (G4). Thus, we havea monochromatic P4 of colour ci, contradicting the assumption that σ is acog-colouring.Therefore, c(H) = k + 1.The following lemma is used to characterize how the number of vertices383.4. Minimum order of k-cog-chromatic graphsof graphs increases when we use the construction introduced in Lemma 3.17.Lemma 3.18. Let f : N+ → N+, be such that f(1) < f(2). If f(n) satisfiesthe following recurrence equationf(n) = 2 · f(n− 1) + 2 · f (dn/2e+ 1) , n ≥ 3,then f(n) = O(2n).Proof. Since f(n) > 0 for all n, f(n) > f(n − 1) and hence f is strictlyincreasing. Let m = dn/2e+ 1 and let g(n) = f(n)2n , then for n ≥ 4,g(n) = g(n− 1) + (12)n−m−1 · g(m) <(1 + (12)n/2−2)· g(n− 1).Taking logarithms on both sides, we have,ln g(n) < ln g(n− 1) + ln(1 + (12)n/2−2)< ln g(n− 1) + (12)n/2−2< ln g(3) + 2 ·n∑i=0(12)i = O(1).Thus, g(n) = O(1) and f(n) = O(2n).Theorem 3.19. For all k ≥ 1, the order of minimum k-cog-chromaticgraphs is O(2k), that is, fc(k) = O(2k).Proof. According to Lemma 3.17, for k ≥ 2,fc(k) ≤ minx+y=k{2 · fc(k − 1) + fc(x) + fc(y)}.When we choose x, y in such a way that |x− y| ≤ 1, we havefc(k) ≤{2 · fc(k − 1) + fc (bk/2c) + fc (dk/2e) when k is odd2 · fc(k − 1) + 2 · fc (k/2) when k is even .Defining f as in Lemma 3.18 with f(i) = fc(i), i = 1, 2, we have fc(k) ≤ f(k)and therefore fc(k) = O(2k).The construction in Lemma 3.17 does not give a tight upper boundfor fc(k). For example, the construction uses 13 vertices to construct a3-cog-chromatic graph from three 2-cog-chromatic graphs and a single ver-tex. However, as Figure 3.5 shows, fc(3) ≤ 10. There may be a general393.5. Cog-critical graphsFigure 3.6: Another view of graph J of c(J) = 3 with 10 verticesconstruction, different from but like the one in Lemma 3.17, that for eachk ≥ 1, uses fc(k) vertices. On the other hand, not all extremal graph func-tions lend themselves to such unified constructions for their correspondingextremal graphs. The functions may be quite different when constrained tosmall inputs as compared to their asymptotic behaviour. Despite this, theview of the graph J in Figure 3.6 shows we can construct a 3-cog-chromaticgraph from two P4s and two vertices. If we could construct a (k + 1)-cog-chromatic graph from two k-cog-chromatic graphs and two vertices, we havefc(k + 1) ≤ 2fc(k) + 2. This view motivates the following conjecture.Conjecture 3.20. For k ≥ 1, fc(k) = 2k + 2k−1 − 2.3.5 Cog-critical graphsIn the study of classic graph colouring, a graph G is colour-critical ifχ(H) < χ(G) for any subgraph H of G. Similarly, we call a graph Gcog-critical if c(H) < c(G) for any induced subgraph H of G. A graphG is k-cog-critical if G is cog-critical and c(G) = k. We consider inducedsubgraphs instead of subgraphs when defining cog-critical graphs becausedeleting an edge from a graph may increase its cog-chromatic number. Forexample, deleting any edge from a C4 results in a P4, while c(P4) > c(C4).3.5.1 Properties of cog-critical graphsWe study several necessary properties of cog-critical graphs.Remark 3.21. A cog-critical graph cannot be a join of two graphs.Proof. Suppose there is a cog-critical graph H = G1 ⊕ G2. Since the joinof any number of graphs is a cograph if and only if the graphs them-403.5. Cog-critical graphsselves are cographs, we have c(H) ≤ max{c(G1), c(G2)} by joining pairsof colour classes from cog-colourings of G1 and G2. Moreover, c(H) ≥max{c(G1), c(G2)} since any cog-colouring of H induces a cog-colouring ofc(Gi), i = 1, 2. Thus, c(H) = max{c(G1), c(G2)}. Suppose c(G1) ≥ c(G2).For any vertex v in G2, H − v ∼= G1 ⊕ (G2 − v) and hencec(H − v) = max{c(G1), c(G2 − v)} = c(G1) = c(H),contradicting the assumption that H is cog-critical.A module [30] of a graph G(V,E) is a subset X ⊆ V satisfying thatfor any vertex v ∈ V \ X, either v is adjacent to every vertex in X or vis not adjacent to any vertex in X. That is, vertices in X have the sameneighbourhood outside X. V (G), ∅, and a single vertex are trivial modulesof G. Modules which are not trivial are called nontrivial modules.Given a graph G and U ⊆ V (G), to shrink U is to replace U by a singlevertex and make it adjacent to all the vertices which were adjacent in G toat least one vertex in U . The resulting graph is denoted by G/U . Let ube the vertex in G/U that corresponds to the U being shrunk and v be anarbitrary vertex in U . According to these definitions, if U is a nontrivialmodule of G, u is connected to the same vertices in G/U as v is in G−(U \v).Thus, for any module U of G and any vertex v ∈ U , G/U ∼= G− (U \ v).Remark 3.22. Every nontrivial module M of a cog-critical graph G satisfiesc(G/M) < c(G).Proof. Let v be an arbitrary vertex in M . Since G/M ∼= G − (M \ {v}),c(G/M) = c(G− (M \ {v})) < c(G).Lemma 3.23. If M is a module of G, then c(G) ≤ c(G/M))+c(G[M ])−1.Proof. Let M = V (G) \M . For any vertex u ∈M , sinceG[M ∪ {u}] = G− (M \ {u}) ∼= G/M,there is a cog-colouring σ of G[M ∪ {u}] using c(G/M) colours. Suppose uis coloured red by σ. By extending σ to colour G such that M are colouredall red, we get a colouring σ′ where all possible monochromatic P4s aresubgraphs of G[M ]. We then use c(G[M ]) − 1 new colours not used by σ′and red to cog-colour M . The resulting colouring is a cog-colouring of G.Therefore, c(G) ≤ c(G/M)) + c(G[M ])− 1.Corollary 3.24. A cog-critical graph G cannot have a nontrivial module Msuch that G[M ] is a cograph.413.5. Cog-critical graphsA restatement of Corollary 3.24 is that no module of a cog-critical graphcan have two vertices. Thus, for any two vertices u, v of a cog-critical graphG, there must be another vertex x of G such that x is adjacent to exactlyone of uv.Lemma 3.25. Let M be a nontrivial module of G and let d(M) be thenumber of vertices not in M but adjacent to vertices in M . If c(G[M ]) +d(M) ≤ c(G/M), then c(G) = c(G/M).Proof. Let N(M) =⋂v∈M N(v). Since M is a module, every vertex notin N(M) is either in M or not adjacent to any vertex in M . Consider acog-colouring σ of G/M . As in the proof of Lemma 3.23, σ can be extendedto a cog-colouring of G by introducing c(G[M ])−1 more colours. Suppose σcolours N(M) with x colours. If x+ c(G[M ]) ≤ c(G/M), then we can reusecolours that σ used to colour vertices in G/M − N(M). This is possiblebecause every vertex in G/M − N(M) is not adjacent to any vertex inM . Thus, we do not need to introduce any new colours and hence c(G) ≤c(G/M). Note that x ≤ d(M). Therefore, if c(G[M ]) + d(M) ≤ c(G/M),then x+ c(G[M ]) ≤ c(G/M) and c(G) ≤ c(G/M). Finally c(G) = c(G/M)because c(G) ≥ c(G/M).Corollary 3.26. A cog-critical graph G cannot have a nontrivial module Msuch that c(G[M ]) + d(M) ≤ c(G/M).3.5.2 Arbitrarily large k-cog-critical graphsAccording to the definition of cog-critical graphs, K1 is the only 1-cog-critical graph and P4 is the only 2-cog-critical graph. In this section, forany fixed k ≥ 3, we describe k-cog-critical graphs with an arbitrarily largenumber of vertices. The constructions in Lemma 3.16 and Lemma 3.17both generate cog-critical graphs when the parts of the construction arecog-critical graphs. Thus, we can use them to create cog-critical graphswith arbitrary number of vertices. However, both constructions increase thecog-chromatic number by one while increasing the number of vertices bytwo or three times. Therefore, both constructions do not provide arbitrarilylarge k-cog-critical graphs with k fixed. In this section, we describe twodifferent constructions that complete this task. Moreover, we provide a wayto construct arbitrarily large k-cog-critical planar graphs where k = 3 and4.Definition 3.27 (J-construction). Let F be a graph with n vertices {v1,· · · , vn}, and H = {H1, · · · , Hn} be a set of disjoint graphs. Define G to be423.5. Cog-critical graphsthe graph with V (G) = V (F ) ∪ (⋃ni=1 V (Hi)) and edges E(G) = E(F ) ∪(⋃ni=1E(Hi ⊕ {vi})). We call G the J-construction from pair (F,H), F theinner graph of G, and H the set of outer graphs of G.In Lemma 3.11, the gadget (Figure 3.4) used in the polynomial reductionis a J-construction where the outer graphs are P4s.Lemma 3.28. Let F be a (k + 1)-colour-critical graph and each Hi ∈ H bea k-cog-critical graph. The J-construction G from pair (F,H) is a (k + 1)-cog-critical graph.Proof. We first categorize induced P4s in G into two types.1. Type-1 P4: The four vertices of the P4 are contained in Hi, for some1 ≤ i ≤ n.2. Type-2 P4: The P4 contains some edge of F .Let Cl = {c1, · · · , cl} be a set of l colours for l ≥ 1. We complete the proofin four claims.Claim 1: c(G) ≤ k + 1.Let σ be a K2-free colouring of F using colours from Ck+1. Extend σ toall of G by obtaining a k-cog-colouring of Hi that uses colours Ck, for each1 ≤ i ≤ n. Neither a Type-1 P4 nor a Type-2 P4 is monochromatic underσ, because each Hi is cog-coloured and there is no monochromatic edge inF . Thus, σ is a (k + 1)-cog-colouring of G and Claim 1 is proved.Claim 2: c(G) > k.Suppose σ is a k-cog-colouring of G using colours from Ck. Since F is notk-colourable, there is a monochromatic edge vivj in E(F ). Suppose vi, vj arecoloured c1. Since c(Hi) = c(Hj) = k, some vertex ui of Hi as well as somevertex uj of Hj are coloured c1. Thus, uivivjuj is a monochromatic inducedP4, contradicting the assumption that σ is a cog-colouring. Therefore, G isnot k-cog-colourable and Claim 2 is proved.Claim 3: For any vertex v of F , c(G− v) ≤ k.Since F is (k+ 1)-colour-critical, there is a K2-free colouring σ of F − v.Extend σ with any k-cog-colouring of Hi using colours Ck for 1 ≤ i ≤ n.Neither a Type-1 P4 nor a Type-2 P4 is monochromatic under σ, becauseeach Hi is cog-coloured and there is no monochromatic edge in F . Thus, σis a k-cog-colouring of G− v, and Claim 3 is proved.Claim 4: For any vertex v in H, c(G− v) ≤ k.Since v is a vertex in H, v is a vertex of Hi, for some 1 ≤ i ≤ n. SinceF is (k + 1)-colour-critical, k ≥ 1, vi is not an isolated vertex in F . Let433.5. Cog-critical graphsvj be an arbitrary vertex which is adjacent to vi in F . Let e = vivj , andlet σ be a K2-free colouring of F − e using colours from Ck. Note that eis monochromatic under σ since otherwise F is k-colourable. Suppose thecolour of vi is c1. We then extend σ to cog-colour Hl with colours from Ck,l 6= i. Since Hi is k-cog-critical, we can further extend σ to all of G − v,with any (k− 1)-cog-colouring of Hi− v using the k− 1 colours in Ck \ {c1}.Then every Type-2 P4 containing vivj cannot be monochromatic under σ,because none of NG(vi)\{vj} is coloured c1, none of NF (vj)\{vi} is colouredc1 and this P4 can have at most one vertex from Hj . Every other Type-2 P4 contains an edge in F with ends of different colours and thus is notmonochromatic. Moreover, there is no monochromatic Type-1 P4 becauseevery Hj is cog-coloured, j 6= i, and Hi − v is cog-coloured. Thus, σ is ak-cog-colouring of G and Claim 4 is proved.By Claims 1 through 4, G is a (k + 1)-cog-critical graph.Theorem 3.29 (Theorem 5 in [52]). There exists a k-colour-critical graph,k ≥ 4, with n vertices if and only if n ≥ k and n 6= k + 1. There exists ak-colour-critical r-uniform hypergraph, k ≥ 3, r ≥ 3, with n vertices if andonly if n ≥ (r − 1)(k − 1) + 1.Theorem 3.30. For any k ≥ 3 and n > 0, there exists a k-cog-criticalgraph G with more than n vertices.Proof. We prove by induction on k.Base Step (k = 3): Let F be a cycle of 2n + 1 vertices and H be a setof 2n + 1 disjoint P4s. Since F is 3-colour-critical and P4 is 2-cog-critical,according to Lemma 3.28, the J-constructionG from (F,H) is a 3-cog-criticalgraph with more than n vertices.Inductive Step: Suppose the statement of the theorem is true for some k,k ≥ 3, and we consider the case k+1. According to Theorem 3.29, there is a(k+ 1)-colour-critical graph F with max{n, k+ 2} vertices. Also, accordingto the inductive hypothesis, there is a k-cog-critical graph H with morethan n vertices. Let H be a set of |V (F )| disjoint copies of H. Accordingto Lemma 3.28, the J-construction G from (F,H) is a (k + 1)-cog-criticalgraph with more than n vertices.A graph is planar if it can be drawn in the plane so that its edgesintersect only at their ends. Such a drawing is called a planar embedding ofthe graph. A graph is outerplanar if it has a planar embedding in whichall vertices lie on the boundary of its outer face. If G is outerplanar, thenG⊕K1 is planar.443.5. Cog-critical graphsCorollary 3.31. For k = 3 and 4, and any n > 0, there is a planar k-cog-critical graph with more than n vertices.Proof. Let F be a cycle of 2n+ 1 vertices and H be a set of 2n+ 1 disjointP4s. As in the proof of Theorem 3.30, the J-construction G from (F,H) is3-cog-critical. Note that, G is also outerplanar (for n = 1, see G′ in Figure3.4). Thus, G is a 3-cog-critical planar graph with more than n vertices.Let G be a set of four disjoint copies of the graph G in the above para-graph. Since G is outerplanar and K4 is planar, the J-construction G′ from(K4,G) is planar. Moreover, K4 is 4-colour-critical and G is 3-cog-critical.According to Lemma 3.28, G′ is 4-cog-critical. Thus, G′ is a 4-cog-criticalplanar graph with more than n vertices.Since planar graphs are 4-colourable, they are 4-cog-colourable. Thus,there does not exist a 5-cog-critical planar graph. The existence of 4-cog-chromatic planar graphs is proved in [25]. Corollary 3.31 provides a construc-tion of 4-cog-chromatic planar graphs which are also 4-cog-critical. Koestergraph [39] is a 4-regular 4-colour-critical planar graph. However, accordingto Remark 3.13, graphs with maximum degree 4 are 3-cog-colourable andhence there is no 4-regular 4-cog-critical planar graph. It is interesting toask whether there is a 4-cog-critical graph with minimum degree 4.The girth of a graph G with at least one cycle is the length of a shortestcycle in G. A graph is triangle-free if it does not contain a cycle or itsgirth is larger than 3. Planar graphs with girth at least 11 are shown tobe 2-cog-colourable [25]. Moreover, it is NP-complete to decide whether atriangle-free planar graph is 2-cog-colourable [16]. Thus, it is interesting toask whether planar graphs with girth at least 5 are 2-cog-colourable.Theorem 3.30 relies on the J-construction and the J-construction relieson the fact there is an arbitrarily large k-colour-critical graphs. In thefollowing, we describe a new construction that does not rely on the existenceof arbitrarily large k-colour-critical graphs, but instead relies on the factthat there are arbitrarily large k-colour-critical hypergraphs, as proved byTheorem 3.29.Definition 3.32 (D-construction). Let H be a graph on n vertices withc(H) = k. Let F be an n-uniform (k + 1)-colour-critical hypergraph. Foreach edge F ∈ F , let H1F , H2F , H3F be three disjoint copies of H and defineHF = (H1F⊕H2F )∪(H2F⊕H3F ). Let G∗ =⋃A,B∈F (HA ⊕HB). For each edgeF ∈ F , let MF be a matching between the vertices of F and V (H1F ). LetG be a graph defined by V (G) = V (F) ∪ V (G∗) and E(G) = E(G∗) ∪453.5. Cog-critical graphs(∪F∈FMF ). We call G the D-construction from F and H, denoted byD(F , H). For each edge F ∈ F , we call HF the satellite graph of F .We will choose the graph H in our D-construction so that proper k-colourings of subhypergraphs of F can be extended to (k+1)-cog-colouringsof G. The following definition and lemma provide the needed properties ofH.Definition 3.33 (Tk graph). Define T2 = P4. For any k > 2, defineTk = T (Tk−1), where the T (G) is the 3+1 construction from G, definedin Definition 3.15.Lemma 3.34. For any k ≥ 2, Tk is k-cog-critical.Proof. Since c(T2) = 2 and c(Tk+1) = c(Tk) + 1 for any k ≥ 2, provedby Lemma 3.16, we have c(Tk) = k for any k ≥ 2. We prove that Tk iscog-critical for any k ≥ 2 by induction on k.Base Step (k = 2): Since any graph of less than 4 vertices is a cograph,T2 is cog-critical.Inductive Step: Suppose Tk is cog-critical for some k ≥ 2. We provethat Tk+1 is cog-critical. Let Tk+1 = (L⊕M)∪ (M ⊕R)∪ (R⊕{s}), whereL,M ,R are three copies of Tk and s is the single vertex. As in the proofof Lemma 3.16, every induced P4 of Tk+1 is either of Type-1 (four verticescontained in one of L, M and R) or Type-2 (s and one vertex from L,Mand R respectively). Let v be an arbitrary vertex of Tk+1. We prove thatc(Tk+1 − v) = k. Let Cl = {c1, · · · , cl} be a set of l colours for any l ≥ 1.We perform a case analysis on v.Case 1: v = s.There is no Type-2 P4 in Tk+1 − v. Since c(Tk) = k, there is a k-colouring σ that cog-colours L, M and R individually, and hence can beextended to Tk+1. Thus, every Type-1 P4 is not monochromatic under σand c(Tk+1 − v) = k.Case 2: v ∈ V (A), where A ∈ {L,M,R}.Without loss of generality, we suppose v ∈ V (L). According to theinductive hypothesis, L is k-cog-critical and thus there is a (k − 1)-cog-colouring σ of L − v using colours from Ck−1. Extend σ to cog-colour Mand R using colours from Ck and set σ(s) = ck. There is no monochromaticType-1 P4 because σ cog-colours L− v, M and R. Every Type-2 P4 is notmonochromatic because every vertex in L− v is not coloured ck. Thus, σ isa k-cog-colouring of Tk+1 − v and c(Tk+1 − v) = k.Therefore, Tk+1 is (k + 1)-cog-critical.463.5. Cog-critical graphsLet τ be a function with domain D and A ⊆ D. Define τA to be therestriction of τ to the set A. That is, τA is a function with domain A suchthat τA(a) = τ(a) for all a ∈ A. If {A1, · · · , Al} is a partition of D, then τ iscompletely determined by {τA1 , · · · , τAl}. Given a graph G and an inducedsubgraph H of G, we simplify the notation of σV (H) as σH , where σ is afunction defined on V (G). A function f : X → Y is constant if all inputshave the same output. That is, for any x1, x2 ∈ X, f(x1) = f(x2).Lemma 3.35. For any k ≥ 2, let Ck = {c1, · · · , ck} be a set of k colours.For any function m : V (Tk)→ Ck, if m is not constant, then Tk has a k-cog-colouring σ using colours from Ck such that σ(v) 6= m(v) for all v ∈ V (Tk).Proof. We prove this lemma by induction on k. We call two functions f andg contrary to each other, denoted by f g, if they have different valuesfor every input common to both domains. The σ of the lemma we areconstructing will be contrary to the given m.Base Step (k=2): Let σ be a colouring of T2 such that σ(v) = c1 ifm(v) = c2 and σ(v) = c2 otherwise. Since T2 is a P4 and m is not constant,σ is a 2-cog-colouring of T2 and σ m.Inductive Step: Let k ≥ 2 and suppose the statement of the lemma istrue for k. We now prove the statement is true for k + 1. Let L,M,Rbe the three copies of Tk and s be the single vertex such that Tk+1 =(L⊕M) ∪ (M ⊕R) ∪ (R⊕ {s}).Claim: For any m : V (Tk+1) → Ck+1 and any A ∈ {L,M,R}, there isalways a colouring τ such that τA is a k-cog-colouring of A and τA mA.Proof of claim: Let A ∈ {L,M,R}. We consider three cases dependingon the size of the range of mA.Case 1. mA is constant.Suppose the range of mA is {c1}. Since A is k-cog-critical, there is ak-cog-colouring τA of A using colours from Ck+1 \ {c1}. It is clear thatτA mA.Case 2. The range of mA has more than one but less than k+ 1 colours.Suppose the range of mA is a subset of Ck. Since A is a copy of Tk,according to the inductive hypothesis, there is a k-cog-colouring τA of Ausing k colours from Ck and τA mA.Case 3. The range of mA has k + 1 colours.Let m′A : V (A)→ Ck be a function such that m′A(v) = mA(v) if mA(v) 6=ck+1 and m′A(v) = c1 otherwise. Now m′A has range of k ≥ 2 colours fromCk. According to the inductive hypothesis, there is a k-cog-colouring τA ofA using k colours from Ck such that τA m′A. For all v with mA(v) 6= ck+1,473.5. Cog-critical graphsmA(v) = m′A(v) 6= τA(v). For all v with mA(v) = ck+1, mA(v) 6= τA(v)because τA(v) 6= ck+1. Thus, τA is contrary to mA.The claim is now proved.Let σ be a colouring of Tk+1 − s such that σ(v) = τ(v) for every v ∈V (Tk+1−s). We complete the proof of the inductive step for case k+1 witha case analysis of the colours used by σL, σM and σR.Case 1. σL, σM and σR do not use the same k colours.Without loss of generality, we suppose the colours used by σL is differentfrom the colours used by σM . Since L and M are both k-cog-critical, therange of σL and the range of σM have exactly (k − 1) colours in common.Thus, there are at least two colours, ci and cj , such that ci is used by σLbut not by σM , and cj is used by σM but not by σL. If m(s) 6= ci, we setσ(s) to ci. If m(s) = ci, we set σ(s) to cj . As in the proof of Lemma 3.16and since σA is a k-cog-colouring of A for all A ∈ {L,M,R}, every possibleinduced P4 of Tk+1 must contain s and have exactly one vertex from L,Mand R respectively. Every such P4 is not monochromatic because either thevertex from L or the vertex from M is not coloured σ(s). Therefore, σ is a(k + 1)-cog-colouring of Tk+1. By construction, σ m.Case 2: σL, σM and σR all use the same k colours.Suppose they all use Ck. If m(s) 6= ck+1, we set σ(s) = ck+1. Then σis a (k + 1)-cog-colouring of Tk+1 with σ m. If m(s) = ck+1, there mustbe some colour ci 6= ck+1 in the range of m because m is not constant. Wethen redefine σ(v) = ck+1 for each v with m(v) = ci, and set σ(s) = ci. Foreach A ∈ {L,M,R}, σA is a k-cog-colouring of A because the redefinitionjust switches ci with ck+1. As in the proof of Lemma 3.16, every possibleinduced P4 of Tk+1 must contain s and have exactly one vertex from L,Mand R respectively. Every such P4 is not monochromatic because s is theonly vertex coloured ci. The resulting σ is a (k + 1)-cog-colouring of Tk+1and σ m.Thus, for any m : V (Tk+1) → Ck+1, if m is not constant, there is a(k + 1)-cog-colouring σ of Tk+1 such that σ m.Therefore the statement of the lemma is true for k + 1.Corollary 3.36. For any k ≥ 2, let F be an empty graph with |V (Tk)| ver-tices, H1F ,H2F ,H3F be three disjoint copies of Tk, MF be a matching betweenV (F ) and V (H1F ). For any vertex v ∈ V (F ), let v′ be the vertex in H1F suchthat vv′ ∈ MF . Define HF = (H1F ⊕ H2F ) ∪ (H2F ⊕ H3F ) ∪ (H3F ⊕ K1) andthe graph J with V (J) = V (F ) ∪ V (HF ) and E(J) = MF ∪ E(HF ). LetCk = {c1, · · · , ck} be a set of k colours. Let τ be a k-colouring of F . If τ isconstant, then for any vertex v ∈ V (J), there is a k-cog-colouring σ of J−v483.5. Cog-critical graphssuch that σF = τ and there is only one monochromatic edge in MF . If τ isnot constant, then there is a k-cog-colouring σ of J such that σF = τ andthere is no monochromatic edge in MF .Proof. We first prove the first part of the lemma. Suppose τ is constant withcolour, say c1. Let v be a vertex of G. We consider three cases dependingon the part of G to which the v belongs.Case 1: v ∈ V (F ).We (k − 1)-cog-colour H1F − v′ using colours from Ck \ {c1} and setσ(v′) = c1. We then k-cog-colour H2F and H3F with colours from Ck. Forevery P4 in J − v, it is either contained in one of {H1F , H2F , H3F } or it has anedge from MF − vv′. Since each one of {H1F , H2F , H3F } is cog-coloured andevery edge in MF except vv′ is not monochromatic, we get a k-cog-colouringof J − v and vv′ is the only monochromatic edge in MF .Case 2: v ∈ V (H1F ).We (k − 1)cog-colour H1F − v with colours from Ck \ {c1}. We thenk-cog-colour H2F and H3F with colours from Ck. For every P4 in J − v, itis either contained in one of {H1F − v,H2F , H3F } or it has an edge from MFdifferent than vv′. Since each one of {H1F − v,H2F , H3F } is cog-coloured andvv′ is the only monochromatic edge in MF , J − v is k-cog-colourable.Case 3: v ∈ V (H2F ) ∪ V (H3F ).Suppose, without loss of generality, v ∈ V (H3F ). We (k − 1)-cog-colourH3F − v with colours from Ck \ {c1} and k-cog-colour H2F with colours fromCk. Then, we choose an arbitrary vertex u′ of H1F , colour u′ with c1 and(k−1)-cog-colour H1F −u′ with colours from Ck \{c1}. For every P4 in J−v,it is either contained in one of {H1F , H2F , H3F − v} or it has an edge from MFdifferent than uu′. Since each one of {H1F , H2F , H3F − v} is cog-coloured anduu′ is the only monochromatic edge in MF , J − v is k-cog-colourable.Now suppose τ is not constant. Since a colouring of H1F is a colouring ofTk, by using τ as the function m in Lemma 3.35, we have a k-cog-colouringof H1F ∪MF using colours from Ck such that there is no monochromaticedge in MF . We can then arbitrarily cog-colour H2F and H3F using coloursfrom Ck. For every P4 in J , it is either contained in one of {H1F , H2F , H3F }or it has an edge from MF . Since {H1F , H2F , H3F } are cog-coloured and everyedge in MF is not monochromatic, we get a k-cog-colouring of G with nomonochromatic edge in MF .Theorem 3.37. Let F be a n-uniform (k + 1)-colour-critical hypergraph,where n = |V (Tk)|. The graph G = D(F , Tk) is (k + 1)-cog-critical.493.5. Cog-critical graphsProof. We first categorize the P4s in G. For any two hyperedges A,B ∈ F ,A 6= B, HA and HB form a join in G. Thus, there is no P4 which has verticesin more than two different satellite graphs. If u1u2u3u4 is a P4 with verticesfrom two different satellite graphs HA and HB, then u2 ∈ V (HA), u3 ∈V (HB) and u1, u4 ∈ A ∪ B. If not, then a triangle is formed between thesatellite graphs. Therefore, any P4, say u1u2u3u4 of G, can be either one ofthe following three types.1. Type-1 P4: The four vertices are contained in a MF ∪ HF for somehyperedge F .2. Type-2 P4: u1 ∈ A, u4 ∈ A, u2 ∈ V (HA), u3 ∈ V (HB), where A andB are two different hyperedges.3. Type-3 P4: u1 ∈ A, u4 ∈ B, u2 ∈ V (HA), u3 ∈ V (HB), where A andB are two different hyperedges.Let Ck = {c1, · · · , ck} be a set of k colours. We break up the proof of thetheorem into four claims.Claim 1: c(G) ≤ k + 1.Let σ be a proper colouring of F using colours from Ck+1. Since there isno monochromatic hyperedge under σ, according to Corollary 3.36, we canextend σ to k-cog-colour G∗ such that ends of each edge in the matchings,∪F∈FMF , are coloured differently. Thus, a P4 of any type must not bemonochromatic under σ. Therefore, σ is a (k + 1)-cog-colouring of G andClaim 1 is proved.Claim 2: c(G) > k.Suppose, to the contrary, G has a k-cog-colouring σ using colours fromCk. Since F is (k + 1)-colour-critical, there is at least one monochromatichyperedge F in F coloured by σ. Suppose the vertices of F are colouredc1. Since H1F , H2F , H3F are all k-cog-critical graphs, c1 must be used bysome vertex u1 in H1F , u2 in H2F and u3 in H3F . But then xu1u2u3 is amonochromatic P4, where xu2 ∈ MF for some x ∈ F , a contradiction.Therefore, c(G) > k and Claim 2 is proved.Claim 3: For any u ∈ F , c(G− u) ≤ k.Since F is (k+1)-colour-critical, there is a proper k-colouring σ of F−v.According to Corollary 3.36, we can extend σ to k-cog-colour G∗ such thatends of each edge in the matchings are coloured differently. Thus, a P4 ofeither type must not be monochromatic under σ. Therefore, σ is a k-cog-colouring of G and Claim 3 is proved.Claim 4: For any u ∈ G∗, c(G− u) ≤ k.503.5. Cog-critical graphsLet A be the hyperedge such that u ∈ V (HA). Since F is (k+ 1)-colour-critical, there is a proper k-colouring σ of F − A. We then extend σ tok-cog-colour G∗ − V (HA) using colours from Ck such that ends of edges in∪F∈F ,F 6=AMF are coloured differently. Because A must be monochromaticunder σ, according to Corollary 3.36, we can extend σ to k-cog-colour MA∪HA such that there is only one monochromatic edge in MA. For any F ∈ F ,MF ∪ HF is k-cog-coloured. Thus, P4s of Type-1 are not monochromatic.Since there is only one monochromatic edge in ∪F∈FMF , P4s of Type-2 andType-3 are not monochromatic. Therefore, σ is k-cog-colouring of G andClaim 4 is proved.By Claim 1 through 4, G is (k + 1)-cog-critical.Using Theorem 3.37, we can have a different proof of Theorem 3.30 basedon the D-construction.Proof. Let k be any fixed integer larger than 2. Then |V (Tk−1)| > 3. Forany n > 0, according to Theorem 3.29, there is a k-colour-critical |V (Tk−1)|-uniform hypergraph F of max{n, |V (Tk−1)|·k, } vertices. According to Theo-rem 3.37, the D-construction G from (F , Tk) is k-cog-critical with more thann vertices.51Chapter 4ConclusionTo the best of our knowledge, we have conducted (for the first time)a probabilistic analysis of super solutions of random instances of SAT andCSPs. While we have focused on the special (but already challenging) caseof (1,0)-super solutions, some of our analysis extends to the case of (a, 0)-super solutions for a > 1. For random instances of CSPs, new analyticalmethods and ideas are needed to obtain a more detailed characterization ofthe behaviour of the super solutions, and we leave this as a future work. Itis also highly interesting to conduct a systematic empirical analysis to fullyunderstand the hardness of solving random instances of (1, 0)-k-SAT as wellas the hardness of solving the projected standard SAT instances, whichmay serve as suite of SAT benchmark with a unique structural properties.We wonder if our analysis can be extended to random instances of otherproblems such as graphical games where solution concepts similar to supersolutions have been used.For the problem of partitioning graphs into cographs, we have studiedseveral problems related to cog-chromatic number of graphs which have notbeen studied before, as far as we know. For example, the order of minimumk-cog-chromatic graphs is studied in Section 3.4. Moreover, methods thatconstruct arbitrarily large graphs with required properties are given in Sec-tion 3.4 and Section 3.5. We are very interested in answering conjecturesmade in Section 3.3 and Section 3.4. For example, does the smallest k-cog-chromatic graphs have 2k + 2k−1 − 2 vertices? We would also like to spendmore time on studying approximation algorithms for c(G) and the hardnessof approximating c(G), where G is an arbitrary graph.52Bibliography[1] D. Achlioptas, The complexity of G-free colourability, Discrete Math,165 (1997), pp. 21–30. → pages 3, 27[2] D. Achlioptas, M. Molloy, L. Kirousis, Y. Stamatiou,E. Kranakis, and D. Krizanc, Random constraint satisfaction: Amore accurate picture, Constraints, 6 (2001), pp. 329–344. → pages 2[3] D. Achlioptas and C. Moore, The asymptotic order of the randomk-SAT threshold, in Proceedings of the 43rd Symposium on Foundationsof Computer Science, FOCS ’02, Washington, DC, USA, 2002, IEEEComputer Society, pp. 779–788. → pages 4, 17[4] D. Achlioptas and Y. Peres, The threshold for random k-SAT is2k ln 2− o(k), in Proceedings of the Thirty-fifth Annual ACM Sympo-sium on Theory of Computing, STOC ’03, New York, NY, USA, 2003,ACM, pp. 223–231. → pages 2, 4, 15, 18[5] M. J. H. Adrian Balint, Anton Belov and M. Ja¨rvisalo, Gen-erating the uniform random benchmarks for sat competition 2013, inSAT Competition 2013: Solver and Benchmark Descriptions, 2013,pp. 97–98. → pages 19[6] N. Alon and J. H. Spencer, The Probabilistic Method, Wiley, 2008.→ pages 8, 9, 10[7] A. Bondy and U. Murty, Graph Theory, Springer, 2008. → pages25, 33[8] J. I. Brown, The complexity of generalized graph colorings, DiscreteApplied Mathematics, 69 (1996), pp. 257 – 270. → pages 3, 27[9] L. Cai, Parameterized complexity of vertex colouring, Discrete AppliedMathematics, 127 (2003), pp. 415 – 429. → pages 2753Bibliography[10] M.-T. Chao and J. Franco, Probabilistic analysis of a generaliza-tion of the unit-clause literal selection heuristics for the k satisfiabilityproblem, Inf. Sci., 51 (1990), pp. 289–314. → pages 2[11] V. Chvatal and B. Reed, Mick gets some (the odds are on his side),in Proceedings of the 33rd Annual Symposium on Foundations of Com-puter Science, SFCS ’92, Washington, DC, USA, 1992, IEEE ComputerSociety, pp. 620–627. → pages 4, 11, 13[12] L. Climent, M. Salido, and F. Barber, Robustness in dynamicconstraint satisfaction problems, International Journal of InnovativeComputing, Information and Control, 8 (2012), pp. 2513–2532.→ pages2[13] D. Corneil, H. Lerchs, and L. Burlingham, Complement re-ducible graphs, Discrete Applied Mathematics, 3 (1981), pp. 163 – 174.→ pages 27[14] N. Creignou and H. Daud, Combinatorial sharpness criterion andphase transition classification for random csps, Information and Com-putation, 190 (2004), pp. 220 – 238. → pages 16[15] J. Culberson and I. Gent, Frozen development in graph coloring,Theoretical Computer Science, 265 (2001), pp. 227–264. → pages 2[16] P. Dorbec, M. Montassier, and P. Ochem, Vertex partitions ofgraphs into cographs and stars, Journal of Graph Theory, 75 (2014),pp. 75–90. → pages 45[17] O. Dubois, Y. Boufkhad, and J. Mandler, Typical random 3-satformulae and the satisfiability threshold, in Proceedings of the EleventhAnnual ACM-SIAM Symposium on Discrete Algorithms, SODA ’00,Philadelphia, PA, USA, 2000, Society for Industrial and Applied Math-ematics, pp. 126–127. → pages 2[18] N. Ee´n and N. So¨rensson, The minisat page, in http://minisat.se,2004. → pages 19[19] P. Erdo¨s and A. Hajnal, On decomposition of graphs, Acta Mathe-matica Academiae Scientiarum Hungarica, 18 (1967), pp. 359–377. →pages 3554Bibliography[20] P. Erdo¨s and A. Re´nyi, On the evolution of random graphs, in Pub-lication of The Mathematical Institute Of The Hungarian Academy OfSciences, 1960, pp. 17–61. → pages 2[21] A. Frieze and M. Molloy, The satisfiability threshold for randomlygenerated binary constraint satisfaction problems, Random Struct. Al-gorithms, 28 (2006), pp. 323–339. → pages 2[22] Y. Gao and J. Culberson, Consistency and random constraint sat-isfaction models, Journal of Artificial Intelligence Research, 28 (2007),pp. 517–557. → pages 2[23] F. Gavril, Algorithms for minimum coloring, maximum clique, min-imum covering by cliques, and maximum independent set of a chordalgraph, SIAM Journal on Computing, 1 (1972), pp. 180–187. → pages 3[24] I. P. Gent, E. Macintyre, P. Prosser, and B. M. Smith, Ran-dom constraint satisfaction: Flaws and structure, Constraints, 6 (2001),pp. 345–372. → pages 21[25] J. Gimbel and J. Nesˇetrˇil, Partitions of graphs into cographs, Elec-tronic Notes in Discrete Mathematics, 11 (2002), pp. 705 – 721. →pages 3, 5, 27, 35, 36, 37, 45[26] M. L. Ginsberg, A. J. Parkes, and A. Roy, Supermodels and ro-bustness, in Proceedings of the Fifteenth National/Tenth Conference onArtificial Intelligence/Innovative Applications of Artificial Intelligence,AAAI ’98/IAAI ’98, Menlo Park, CA, USA, 1998, pp. 334–339. →pages 1[27] C. Gomes and T. Walsh, Randomness and structure, in Handbookof Constraint Programming, Elsevier, 2006, pp. 639–664. → pages 2[28] T. F. Gonzalez, Handbook of Approximation Algorithms and Meta-heuristics, Chapman & Hall/CRC, 2007. → pages 31[29] M. Habib and C. Paul, A simple linear time algorithm for cographrecognition, Discrete Appl. Math., 145 (2005), pp. 183–197. → pages27, 34[30] M. Habib and C. Paul, A survey of the algorithmic aspects of modulardecomposition, Computer Science Review, 4 (2010), pp. 41 – 59. →pages 4155Bibliography[31] F. Harary, Graph Theory, Addison-Wesley, 1969. → pages 33[32] R. B. Hayward, Weakly triangulated graphs, Journal of CombinatorialTheory, Series B, 39 (1985), pp. 200 – 208. → pages 28[33] R. B. Hayward, S. Hougardy, and B. A. Reed, Polynomial timerecognition of P4-structure, in Proceedings of the Thirteenth AnnualACM-SIAM Symposium on Discrete Algorithms, SODA ’02, Philadel-phia, PA, USA, 2002, Society for Industrial and Applied Mathematics,pp. 382–389. → pages 29[34] E. Hebrard, B. Hnich, and T. Walsh, Super solutions in constraintprogramming, in Proceedings of First International Conference on Inte-gration of AI and OR Techniques in Constraint Programming for Com-binatorial Optimization Problems (CPAIOR’04), 2004, pp. 157–172. →pages 1, 2, 6, 7[35] C. T. Hoa`ng and V. B. Le, P4-free colorings and P4-bipartite graphs,Discrete Mathematics and Theoretical Computer Science, (2001),pp. 109–122. → pages 3, 27, 29[36] R. M. Karp, Reducibility among combinatorial problems., in Complex-ity of Computer Computations, The IBM Research Symposia Series,Plenum Press, New York, 1972, pp. 85–103. → pages 34[37] P. Kelsen, S. Mahajan, and H. Ramesh, Approximate hypergraphcoloring, in Algorithm Theory SWAT’96, vol. 1097 of Lecture Notesin Computer Science, Springer Berlin Heidelberg, 1996, pp. 41–52. →pages 36[38] J. Kleinberg and E´va Tardos, Algorithm Design, Addison Wesley,2009. → pages 30[39] G. Koester, Note to a problem of T. Gallai and G. A. Dirac, Com-binatorica, 5 (1985), pp. 227–228. → pages 45[40] H. Lerchs, On cliques and kernels, Tech Report Dept. of Comp. Sci.University of Toronto, (1971). → pages 3, 27[41] B. D. McKay and A. Piperno, Practical graph isomorphism, II,Journal of Symbolic Computation, 60 (2014), pp. 94 – 112. → pages 37[42] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge,1995. → pages 956Bibliography[43] H. Mu¨ller, Hamiltonian circuits in chordal bipartite graphs, DiscreteMath., 156 (1996), pp. 291–298. → pages 29[44] J. Nastos and Y. Gao, Familial groups in social networks, SocialNetworks, 35 (2013), pp. 439–450. → pages 1[45] B. O’Sullivan, Opportunities and challenges for constraint program-ming, in Proceedings of AAAI’12 - Invited Spotlight Paper, 2012. →pages 2[46] M. M. Paul Dorbec and P. Ochem, Vertex partitions of graphs intocographs and stars, Journal of Graph Theory, 75 (2014), pp. 75–90. →pages 27[47] S. Poljak, A note on stable sets and colorings of graphs., Commentat.Math. Univ. Carol., 15 (1974), pp. 307–309. → pages 29[48] A. Roy, Fault tolerant boolean satisfiability, Journal of Artificial Intel-ligence Research (JAIR), 25 (2006), pp. 503–527. → pages 2[49] S. E. Schaeffer, Graph clustering, Computer Science Review, 1(2007), pp. 27 – 64. → pages 1[50] B. M. Smith and M. E. Dyer, Locating the phase transition in bi-nary constraint satisfaction problems, Artificial Intelligence, 81 (1996),pp. 155 – 181. → pages 21[51] L. Stewart, Cographs : a Class of Tree Representable Graphs, Tech-nical report, Department of Computer Science, University of Toronto,1978. → pages 27[52] B. Toft, On color-critical hypergraphs, Colloquia Mathematica Soci-etatis Ja´nos Bolyai, (1973), pp. 1445–1457. → pages 44[53] G. Verfaillie and N. Jussien, Constraint solving in uncertain anddynamic environments: a survey, Constraints, 10 (2005), pp. 253–281.→ pages 1[54] K. Xu and W. Li, Many hard examples in exact phase transitions withapplication to generating hard satisfiable instances, tech. rep., Theoret-ical Computer Science, 2003. → pages 257Bibliography[55] M. Yannakakis, Node- and edge-deletion NP-complete problems, inProceedings of the Tenth Annual ACM Symposium on Theory of Com-puting, STOC ’78, New York, USA, 1978, ACM, pp. 253–264. → pages29, 3458
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- A study on generalized solution concepts in constraint...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
A study on generalized solution concepts in constraint satisfaction and graph colouring Zhang, Peng 2014
pdf
Page Metadata
Item Metadata
Title | A study on generalized solution concepts in constraint satisfaction and graph colouring |
Creator |
Zhang, Peng |
Publisher | University of British Columbia |
Date Issued | 2014 |
Description | The concept of super solutions plays a crucial role in using the constraint satisfaction framework to model many AI problems under uncertain, dynamic, or interactive environments. The availability of large-scale, dynamic, uncertain, and networked data sources in a variety of application domains provides a challenge and opportunity for the constraint programming community, and we expect that super solutions will continue to attract a great deal of interest. In the first part of this thesis, we study the probabilistic behaviour of super solutions of random instances of Boolean Satisability (SAT) and Constraint Satisfaction Problems (CSPs). Our analysis focuses on a special type of super solutions, the (1,0)-super solutions. For random k-SAT, we establish the exact threshold of the phase transition of the solution probability for the cases of k = 2 and 3, and we upper and lower bound the threshold of the phase transition for the case of k ≥ 4. For random CSPs, we derive a non-trivial upper bound on the threshold of phase transitions. Graph colouring is one of the most well-studied problems in graph theory. A solution to a graph colouring problem is a colouring of the vertices such that each colour class is a stable set. A relatively new generalization of graph colouring is cograph colouring, where each colour class is a cograph. Cographs are the minimum family of graphs containing a single vertex and are closed under complementation and disjoint union. We define the cogchromatic number of a graph G as the minimum number of colours needed by a cograph colouring of G. Several problems related to cograph colouring are studied in the second part of this thesis, including properties of graphs that have cog-chromatic number 2; computational hardness of deciding and approximating the cog-chromatic number of graphs; and graphs that are critical in terms of cog-chromatic numbers. Several interesting constructions of graphs with extremal properties with respect to cograph colouring are also presented. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2014-08-19 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivs 2.5 Canada |
DOI | 10.14288/1.0074361 |
URI | http://hdl.handle.net/2429/50022 |
Degree |
Master of Science - MSc |
Program |
Interdisciplinary Studies |
Affiliation |
Graduate Studies, College of (Okanagan) |
Degree Grantor | University of British Columbia |
GraduationDate | 2014-09 |
Campus |
UBCO |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2014_september_Zhang_Peng.pdf [ 725.24kB ]
- Metadata
- JSON: 24-1.0074361.json
- JSON-LD: 24-1.0074361-ld.json
- RDF/XML (Pretty): 24-1.0074361-rdf.xml
- RDF/JSON: 24-1.0074361-rdf.json
- Turtle: 24-1.0074361-turtle.txt
- N-Triples: 24-1.0074361-rdf-ntriples.txt
- Original Record: 24-1.0074361-source.json
- Full Text
- 24-1.0074361-fulltext.txt
- Citation
- 24-1.0074361.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0074361/manifest