Assignment 1
COMP6741: Algorithms for Intractable Problems
Name: insert your name here
Student number: insert your student number here
1 Instructions
Assignment 1 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 Tuesday, 7 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.
2 Background
The goal of this assignment is to show that Dominating Clique is NP-complete on graphs whose vertex set can be partitioned into triangles (i.e., cliques of size 3).
Note. Unless otherwise specified, graphs are always finite, simple (no loops and no multi-edges), and undirected. Definition 1. A triangle is a clique of size 3. A graph is triangle-partitionable if its vertex set can be partitioned
into triangles.
Let us now define the notions of a dominating set and dominating clique.
Definition 2. Let G = (V, E) be a graph. A vertex subset S ⊆ V is a dominating set in G if each vertex v ∈ V \ S
is adjacent to a vertex in S. The set S is a dominating clique in G if it is both a dominating set and a clique in G. 1
c This graph is not triangle-partitionable since its number of vertices is not divisible
c This graph is triangle-partitionable since {{a, b, c}, {d, e, f }} is a partitioning of the vertex set into two triangles.
Programming Help
We can now define the Dominating Set and the Dominating Clique problems, as well as their restrictions to triangle-partitionable graphs.
Dominating Set
Input: A graph G = (V,E) and an integer k ≥ 0 Question: Does G have a dominating set of size at most k?
Dominating Clique
Input: A graph G = (V,E) and an integer k ≥ 0
Question: Does G have a dominating clique of size at most k?
Note. If you consult the literature about Dominating Clique, be aware that some sources define it without any size restriction on the dominating clique.
TP Dominating Set
Input: A triangle-partitionable graph G = (V, E) and an integer k ≥ 0 Question: Does G have a dominating set of size at most k?
TP Dominating Clique
Input: A triangle-partitionable graph G = (V, E) and an integer k ≥ 0 Question: Does G have a dominating clique of size at most k?
The previous example graphs with k = 2 are Yes-instances for both Dominating Set and Dominating Clique since {d, c} is a dominating set and a clique of size 2.
The NP-completness of Dominating Set is well-established [1], and your solutions may rely on the following theorem.
Theorem 3. Dominating Set is NP-complete.
Note. NP-hardness can be shown by a reduction from Vertex Cover, where we remove all isolated vertices, and add a path of length 2 (two new edges and one new vertex for each such path) between every two adjacent vertices. The integer k remains the same. Based on this, you should be able to prove Theorem 3. Consult the literature or online resources if you have trouble.
3 Exercises
Exercise 1. [50 points] Show that TP Dominating Set is NP-hard.
You may reduce from any NP-hard problem we have seen in the lectures (CNF-SAT, 3-CNF SAT, Clique, Inde- pendent Set, Vertex Cover, Hamiltonian Cycle, etc.) or from Dominating Set.
Hint. If you reduce from Dominating Set, it is natural to at least triple the number of vertices, since in each instance for TP Dominating Set the number of vertices of the graph is divisible by 3.
Exercise 2. [40 points] Show that TP Dominating Clique is NP-hard.
Hint. One possible solution strategy is to reduce from TP Dominating Set. You may always rely on statements from previous exercises, even if you did not completely solve them.
Exercise 3. [10 points] Show that TP Dominating Clique is NP-complete.
References
[1] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP- Completeness. W. H. Freeman & Co., 1979.
浙大学霸代写 加微信 cstutorcs
A Appendix: Scenario
This appendix provides a motivation for the studied problem. Graph problems are usually very general and abstract, which also means that they have applications in many diverse settings. They often capture the core complexity of real-life computational tasks which often have additional constraints and more complex objective functions.
Consider the construction of a secure, reliable, robust, fast real-time communication network, where devices are always deployed in triples for reliability, robustness, and redundancy reasons. We have enough budget to upgrade k nodes and massively increase their thoughput. These k nodes will form the backbone of this communication network, and ideally they are all connected to each other.
In this scenario, we are given a graph, which is undirected if we assume communication channels are 2-way. A backbone of k nodes needs to reach each other node in one hop, meaning the backbone forms a dominating set. If the nodes of the backbone are all interconnected, they form a clique. Now, the Dominating Clique is well-studied, but the designer of the network wonders whether the presence of triples makes the problem tractable. These triples are inter-connected, which makes the graph triangle-partitionable.
One might wonder about variants of the problem where the network designer wishes to find a dense backbone or a backbone with smallest possible diameter. Note that Dominating Clique is a special case of these problems and NP-hardness of Dominating Clique imples NP-hardness of these variants.
Code Help