NAME OF CANDIDATE: insert your name here STUDENT ID: insert your student ID here
THE UNIVERSITY OF NEW SOUTH WALES
COMP6741: ALGORITHMS FOR INTRACTABLE PROBLEMS – Exam
1. NOMINAL LENGTH OF EXAM – 2 hours
Copyright By PowCoder代写 加微信 powcoder
3. THIS EXAMINATION PAPER HAS 3 PAGES
4. TOTAL NUMBER OF QUESTIONS – 3
5. TOTAL MARKS AVAILABLE – 100
6. ALL QUESTIONS ARE NOT OF EQUAL VALUE. MARKS AVAILABLE FOR EACH QUES- TION ARE SHOWN IN THE EXAMINATION PAPER.
7. ANSWERS ARE SUBMITTED ELECTRONICALLY AS A PDF FILE ON MOODLE. There is no restriction on the software or technology used to create this PDF file.
SPECIAL INSTRUCTIONS
8. ANSWER ALL QUESTIONS.
9. THIS IS AN OPEN-BOOK EXAM. Feel free to consult textbooks, lecture notes, exercise solutions, web pages, etc.
10. DO NOT COMMUNICATE WITH OTHER PEOPLE DURING THE EXAM. DO NOT MAKE THE QUESTIONS OR SOLUTIONS AVAILABLE TO OTHERS.
11. IF YOU NEED TO GET IN TOUCH WITH THE LECTURER, PLEASE POST ON OUR TEAMS CHANNEL. SEND THE QUESTION AS A PRIVATE TEAMS MESSAGE TO THE LECTURER IF IT REVEALS A PARTIAL SOLUTION OR HINT.
Page 1 of 3 Please see over
Your answers may rely on theorems, lemmas and results stated in the lecture notes and exercise sheets of this course. If your answers are inspired by other people’s work, please cite appropriate references.
1 ETH Lower Bound
Recall that a K4 is a complete graph on 4 vertices, i.e., a 4-vertex graph with all 6 edges.
[15 marks]
K4-Free Induced Subgraph (K4-FIS)
Input: Graph G = (V, E), integer k
Question: Is there a subset of vertices S ⊆ V with |S| ≥ k such that G[S] does no have a K4 as a
NB. Note that a graph has no K4 as a subgraph if and only if it has no K4 as an induced subgraph.
Prove that K4-FIS has no 2o(|V |) time algorithm if the Exponential Time Hypothesis (ETH) is
Hint: You may want to rely on the fact that Vertex Cover has no 2o(|E|) time algorithm if the ETH is true. Alternatively, you could rely on the fact that Vertex Cover has no 2o(|V |) time algorithm if the ETH is true.
[40 marks] We consider two problems related to the 3-Sat problem. Let F be a propositional formula in conjunctive
normal form (CNF).
The formula F is a 3-CNF formula if each clause contains at most 3 literals.
The formula F is a 0-Val formula if each clause contains a negative literal, i.e., a literal that is the negation of a Boolean variable.
Local-Search-3-Sat (LS-3-Sat)
Input: A 3-CNF formula F , an assignment α : var(F ) → {0, 1}, and an integer k
Parameter: k
Question: Is there an assignment β : var(F ) → {0, 1} that differs with α on at most k variables
and that satisfies F?
Weak Backdoor from 3-CNF to 0-Val (WB(3CNF,0-Val))
Input: A 3-CNF formula F and an integer k
Parameter: k
Question: Is there an assignment τ : S → {0,1} to at most k variables S such that F[τ] is a
satisfiable 0-Val formula?
1. Design an O∗(3k) time algorithm for LS-3-Sat.
2. Show that 3-Sat can be solved in O∗(3n/2) ⊆ O∗(1.7321n) time, where n = |var(F)|.
3. Show that WB(3CNF,0-Val) has a O∗(3k) time algorithm.
[15 marks]
[10 marks]
[15 marks]
Hint: If you fail to solve some question, assume the existence of a solution of that question when answering subsequent questions.
Page 2 of 3 Please see over
3 Weighted 2-Regular Vertex Deletion
[45 marks] In a multigraph G = (V, E), each edge contributes 1 to the degree of each of its endpoints; in case the
edge connects a vertex to itself (self-loop), it contributes 2 to the degree of this vertex.
Consider the Weighted 2-Regular Vertex Deletion problem. A 2-regular multigraph is a multigraph where every vertex has degree 2. That is, it is a disjoint union of cycles – this includes isolated 1-cycles (a vertex connected only to itself via one self-loop) and 2-cycles (a connected component
with two vertices connected to each other by two edges).
Weighted 2-Regular Vertex Deletion (W2RVD)
Input: Multigraph G = (V, E), a weight function ω : V → N+ assigning an integer ω(v) ≥ 1 to every vertex v ∈ V , and an integer k
Parameter: k
Question: Is there a set S ⊆ V with weight v∈S ω(v) at most k such that G − S is a 2-regular
multigraph?
1. Design simplification rules that transform (G,ω,k) into an equivalent instance (G′,ω′,k′) such that
(a) G′ has no vertex of degree at most 1, and [5 marks] (b) G′ has no degree-2 vertex with a neighbor of degree 2 (and G′ has no isolated 1-cycles, which
is a special case). [10 marks]
2. Show that a multigraph with minimum degree at least 2 and no degree-2 vertex with a neighbor
of degree 2 has average degree at least 2.4. [15 marks]
3. Show that there is a (possibly randomized) algorithm for W2RVD with running time O∗(ck) for
some constant c > 1.
[15 marks]
Page 3 of 3
End of Paper
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com