Assignment 3
COMP6741: Algorithms for Intractable Problems
Name: insert your name here
Student number: insert your student number here
Copyright By PowCoder代写 加微信 powcoder
1 Instructions
This assignment is an individual assignment. For the solutions to this assignment, you may rely on all theorems, lemmas, and results from the lecture notes. If any other works (articles, Wikipedia entries, lecture notes from other courses, etc.) inspired your solutions, please cite them and give a list of references at the end.
If you have questions about this assignment, please post them to the forum.
Due date. This assignment is due on Thursday, 23 June 2022, at 5 pm, Sydney time. Submitting x hours after the deadline, with x > 0, reduces the obtained mark by 5 · ⌈x/24⌉ marks. No submissions will be accepted 5 days (120 hours) or more after the deadline.
How to submit. Submit a PDF with your solutions to the exercises in Moodle. The first page of the PDF must contain your name and student number.
Note. You may always rely on the claims of previous questions, even if you failed to solve / prove them. 2 Background
A P3 is a path on 3 vertices.
We consider a problem that requires to find k vertex-disjoint P3s in a graph. These 3-vertex paths must not share any vertices and they need to be subgraphs of the input graph (but not necessarily induced subgraphs). In other words, it should be possible to delete vertices and edges from the input graph so that we get a disjoint union of k P3s.
Example The pair (H, 4) is a yes-instance, when H denotes the following graph:
Disjoint P3s
Input: A graph G = (V, E) and an integer k
Parameter: k
Question: Does G have k vertex-disjoint P3s as subgraphs?
The corresponding optimisation problem has as input a graph G, the feasible solutions are all the subgraphs that form a disjoint union of P3s, and the objective is to maximize the number of P3s.
The Greedy-DP3 algorithm proceeds as follows:
Algorithm Greedy-DP3(G)
Input : A graph G = (V,E)
Output: An integer k such that G has k disjoint P3s.
if ∆(G) < 2 then return 0
// G has no vertex with degree at least 2
// Select a vertex c with smallest degree among all vertices with degree at least 2
c ← arg minv∈V {d(v) : d(v) ≥ 2}
// Select 2 neighbors of c with smallest degree
Let L ⊆ N(c) such that |L| = 2, and for each u ∈ N(c) \ L we have that d(u) ≥ maxl∈L{d(l)}
// We have found a P3 with internal node c and leaves L, delete the P3 and recurse return 1 + Greedy-DP3(G − ({c} ∪ L))
In this assignment we show that Greedy-DP3 is a 3-approximation algorithm for the optimisation problem and that the parameterized decision problem has a kernel of size O(k3).
3 Exercises
Exercise 1.
Exercise 2.
Exercise 3.
Give an input where Greedy-DP3 does not necessarily1 compute an optimal solution. [15 points] Show that Greedy-DP3 is a 3-approximation algorithm for Disjoint P3s. [15 points] Your colleague proposes the following algorithm and claims it is a 2-approximation algorithm for
Disjoint P3s. Identify two main issues with their claim.
Algorithm LongPathHeuristic(G)
Input : A graph G = (V,E)
Output: An integer k such that G has k disjoint P3s.
l ← length of a longest path in G return ⌊(l + 1)/3⌋
[10 points]
1the word necessarily emphasizes that if the algorithm is not explicit about choices it makes, we may assume that it makes the worst possible choices on a given input instance.
Exercise 4. Design (no need to prove soundness) simplification rules for Disjoint P3s that transform the input graph into a graph
with no vertex of degree 0,
with no vertex of degree 1 with a neighbor of degree 1, and
with no vertex that is adjacent to at least 2 vertices of degree 1.
[15 points]
Exercise 5. Let S denote the set of vertices with degree at least 3k in G. Design simplification or halting rules for the following two cases:
|S|≥k,and
G − S has at least (3k)2 vertices with degree at least 2.
and show that they are sound. [25 points] For the next exercise, we also assume that there exist simplification rules that handle the following cases:
|S|≤kandG−Scontainsatleast2|S|verticesthathavedegree0inG−S,and |S| ≤ k and G − S contains at least |S| connected components with 2 vertices.
Exercise 6. Show that Disjoint P3s has a kernel of size O(k4). [20 points] Note. We need to upper bound the number of vertices and the number of edges of the resulting graph by O(k4).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com