The Australian National University Semester 1, 2022 Research School of Computer Science Tutorial 10
Theory of Computation
This tutorial sheet contains way more exercises that you will be able to solve or discuss in the tutorial.
Exercise 1 Scheduling
Copyright By PowCoder代写 加微信 powcoder
Given n tasks T = {T1,…,Tn}, and k workers, we would like to produce a schedule to get the tasks done by workers as soon as possible.
We assume each task takes a single unit of time, and any work can complete any task. Unfortunately, some tasks depend on other tasks, so we also have a set of constraints M ⊆ T × T , where (Ti, Tj ) ∈ M means that task Ti must be completed before task Tj.
Let the unit-time-scheduling-problem (UTSP) be the problem of, given n tasks T = {T1,…,Tn}, k workers, and a time limit t, does there exist a schedule of the tasks, such that
• Each task is assigned to one time unit between 1 and t,
• At most k tasks are assigned to any one time unit, and
• The constraints M are respected: that is, if (Ti,Tj) ∈ M then task Ti must be assigned to an earlier time unit than Tj.
(hard) Show that if we restrict UTSP to only ever having 1 worker, then it is in P.
Solution. If t < n, the answer is no. Otherwise, construct a directed graph G = (T,M), with the nodes as the tasks, and the timing constraints as the edges. Construct a sequence Xi by first adding all nodes with no inbound edges, corresponding to tasks that do not depend on any other tasks. (If no such tasks exists, the answer is no.) Then, progressively add nodes to the end of the sequence by performing a breadth-first search, only adding a node if all of the parent nodes are already in the sequence. (If all such unexplored nodes are dependant on an unexplored task, then the tasks have a circular dependency, and the answer is no.) Once completed, we have an enumeration of the tasks X1, . . . Xn. Assign Xi to be executed on the i’th time unit, and we have a valid schedule.
It is clear that all the operations above (constructing the graph, adding the orphan nodes to the sequence, and performing the breadth first search) are polytime operations.
The proof is too difficult to do here, but UTSP is NP-Complete.
Exercise 2 Graph Colouring
Let G = (V,E) be an undirected connected graph, and k be a natural number. A k-colouring of G is a function f : V → {1,...,k} such that (vi,vj) ∈ E ⇒ f(vi) ̸= f(vj), i.e. vertices that share an edge cannot share the same colour.
We say that a graph is k-colourable if a k-colouring exists, and we let k-COLOUR denote the descision problem if a graph is k-colourable.
1. Show that the Petersen graph (Figure 1) is 3-colourable but not 2-colourable.
We can 3-colour the graph as shown1 (Figure 2). We note that a 2-colouring is impossible, as the colours would have to alternate around the outside border, but the border has 5 vertices, so there must be two adjacent vertices of the same colours.
1 https://upload.wikimedia.org/wikipedia/commons/9/90/Petersen_graph_3- coloring.svg
Figure 2: 3-colouring of the Petersen graph
2. Find a family of graphs G2 , G3 , . . . such that Gi is i-colourable but not (i − 1)-colourable.
Solution. Choose Gi to be the totally connected graph with i vertices. Given every vertex is connected to every other, we must use i colours and no less, otherwise by pidgeonhole principle, there will be two vertices with the same colour that are connected (as all pairs of vertices are connected.)
3. Show that 1-COLOUR and 2-COLOUR are in P .
Solution. 1-COLOUR is trivial, as it’s possible only for graphs with no edges.
For 2-COLOUR, choose some vertex v at random. WLOG this vertex must be colour 1, as any 2-colouring is still a valid 2-colouring if all the colours are flipped. Then, we can proceed with a breadth-first search from v, colouring each uncoloured node the opposite colour of it’s parent (as the choice of colour is forced to be different.) Repeat until all nodes are coloured, which is clearly polytime. Since there were no choices (other than the initial starting node and colour, which don’t matter) then this is the only 2-colouring, if one such colouring exists. Check if the result of running this algorithm is indeed a valid 2-colouring, and return yes or no as appropriate.
This is polytime, as breadth first search is a polytime operation.
4. (hard) Show that 3-COLOUR is NP-Complete.
(Hint: Reduce from 3SAT. Call the three colours False, True and Other. As a starting point, consider the gadgets2 below.)
Color Palette
x1 ¬x1 OR gadget Variable
Solution. Given a valid 3-colouring, we can verify it by checking for each node that all adjacent nodes are of a different colour, taking O(n2) time for n nodes, so clearly 3-COLOUR is in NP.
It suffices to prove that 3-COLOUR is NP-Hard via reduction from 3SAT.
We add three vertexes O,T,F, and add edges to make them a triangle. WLOG colour them Other (blue), True (green) and False (red). For every variable xi, create the vertices xi and ¬xi, and add edges so O,xi,¬xi forms a triangle, for all i. Since it forms a triangle, each xi has to be true, and ¬xi coloured false, or the other way around.
The following graph provides an example colouring, corresponding to an assignment of variables.
... xn ¬xn
For each clause of the form a ∨ b ∨ c where a, b, c are literals, we replicate the above gadget twice,
but use the already existing vertices for literals instead of creating new ones.
For the node out in the gadget, we form a triangle with the vertices out, F and O, which forces the
colour of out to be True.
2A gadget is a term used for a structure that can simulate the variables or clauses in Boolean formulas.
Now, given a variable assignment that makes a ∨ b ∨ c false, then all of the literals a, b, c are false, then those nodes would be coloured False. By enumerating combinations for V1 and V2, V3 must be coloured False. Since c is False, and out is (forced to be) True, V5 must be coloured Other. But then V4 is adjacent to three nodes of different colours, so no colour will fit. Hence the gadget is non-3-colourable.
Now, given a variable assignment that makes a ∨ b ∨ c true, then at least one of the literals a, b, c is true.
• IfcisTrue,anda̸=b,thencolourV1 =b,V2 =a,V3 =Other,V4 =False,V5 =Other.
• IfcisTrue,anda=b,thencolourV1 =¬a,V2 =Other,V3 =a,V4 =Other,V5 =False.
• IfcisFalse,anda̸=b,thencolourV5 =Other,V4 =False,V3=Other,V1 =bandV2 =a.
• IfcisFalse,anda=b,thena=b=True(astheycannotallbeFalse).Then,colourV5 = Other, V4 = False, V3 = True, V1 = False, V2 = Other.
In any case, the gadget is 3-colourable.
Hence, we have constructed a subgraph that is 3-colourable iff the assignment of variables makes
a∨b∨c true.
Then, for each clause build one of these gadgets, and then the entire graph is 3-colourable iff each
of the clauses is true under the variable assignment, iff the entire boolean expression is satisfiable.
The construction of this graph is polytime, as we set up the graph for assignments (linear in the number of variables) and the many gadgets (each of which is constant size, and there are as many as there are clauses.)
Exercise 3 Student Timetabling
Given a set of students S, a set of courses C, and a set of timeslots T, and an enrollment function3 e : S → P(C), we would like to assign courses to timeslots such that no student has two of their courses running at the same time.
Formally, we want to know if there exists a timetabling function t : C → T such that for all students, all of their classes are running at different timeslots, that is, t should satisfy
∀s ∈ S(∀c1, c2 ∈ e(s), c1 ̸= c2 ⇒ t(c1) ̸= t(c2))
We let TIMETABLE denote the problem of whether such a timetabling function exists.
(hard) Show that TIMETABLE is NP-Complete. You might want to consider reducing from 3-Colour.
Solution. We reduce from 3-COLOUR. Given a graph G = (V, E) and 3 many colours {1, 2, 3}, we add a student for every edge S = E, and each student is enrolled in the two courses on either end of the edge that represents them, so if s = (vi,vj) then e(s) = {vi,vj}. We choose the timeslots to be the 3 colours {1, 2, 3}.
Then, we can assign the courses to timeslots in a non-clashing way if and only if G was 3-colourable. Why? Suppose G was k-colourable. Then no two vertices that share an edge have the same colour, so for
every student, their two classes run on different timeslots, so nobody has a clash.
Conversly, if G were not k-colourable, then for any assignment of colours to vertices, there must exist an edge with the same coloured vertex on both ends. This means there exists a student for which both of their classes are running at the same time, which is a clash.
Since 3-COLOUR is NP-Complete, then TIMETABLE must be NP-Hard.
Also, TIMETABLE is NP, as given a valid timetable function, we can check for all students that none of their classes are running at the same time, which for l ≤ n students, each with at most m ≤ n classes, it takes O(n2) time to check if a student is enrolled in clashing classes (just check all pairwise combinations of their enrolled classes) and then repeat for each student, O(n3), polytime.
3Recall that P(S) denotes the power set of S, the set of all subsets of S
Exercise 4 Partition into cliques
One can draw the network of friendships at a party as a graph, with attendees as nodes, and an edge between two nodes indicates those attendees are friends. Given a subset S of attendees at the party, if everyone in S knows each other (any two nodes in S share an edge) then we say that S is a clique.
Given a friendship graph G = (V, E), if there exists a partition4 {P1, . . . Pk} of V such that each Pi is a clique, then we say that G has a valid partition into k cliques.
Let the PARTITION-CLIQUE problem be as follows: Given a graph G and an integer k, does there exist a partition of the graph into no more than k cliques?
(hard) Prove that PARTITION-CLIQUE is NP-Complete. reduction from 3SAT is messy. Try reducing from a different NP-Complete problem instead.
Solution. We prove via reduction from 3-COLOUR. Fix k = 3. Take an instance of the 3-COLOUR problem (i.e. a graph G), and compute the graph compliment G′ = (V, E′), where
E′ = {(ei,ej) : (ei,ej) ̸∈ E,ei ̸= ej}
i.e. the graph formed by using the same verticies as G, but adding all the edges that G is missing, and
removing all the edges that G had.
Then, if the original graph is 3-colourable, then whatever nodes in the graph are of the same colour, form a clique in the complement graph, as if the nodes are of the same colour in the original graph, they cannot be adjacent, which means they are adjacent in the complement graph.
Hence the complement graph satisfies PARTITION-CLIQUE.
Now, if the graph is not 3-colourable, then the complement graph cannot possibly be an instance of PARTITION-CLIQUE for k = 3, for if it was, then we have three groups of nodes in the complement graph, and for each group, the nodes pairwise don’t share an edge. This means in the original graph, there are three groups that all pairwise share edges with other nodes in their group, and hence provides a partition into 3 cliques.
4A partition P = {P1,...Pk} of a set V is a collection of subsets Pi of V such that P1∪P2∪...∪Pn = V and Pi∩Pj = ∅ for any i ̸= j.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com