COMP6741: Algorithms for Intractable Problems - Assignment 2: Nonblocker
Assignment 2
COMP6741: Algorithms for Intractable Problems
Name: insert your name here
Student number: insert your student number here
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. 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 improve on the best known kernel for Nonblocker.
Definition 1. Let G = (V,E) be a graph. A subset of vertices S ⊆ V is a dominating set of G if each vertex
v∈V\ShasaneighborinS.AsubsetofverticesS⊆V isanonblockerofGifV\SisadominatingsetofG. Example:
This graph has a nonblocker of size 4 (highlighted) and {c, d} form a dominating set of size 2.
If we think of the graph as the state space of a system, and we are in a state that belongs to the nonblocker S = {a,b,e,f}, then we can escape from S by
de transitioning via one edge to a state that is not in S. f
Let us now define the Nonblocker problem.
The current smallest kernel for Nonblocker relies heavily on an upper bound on the domination number of graphs of minimum degree at least 2.
Definition 2. The domination number of a graph G is the size of a smallest dominating set of G.
Theorem 3 ([1, 4]). Every connected graph on n ≥ 8 vertices with minimum degree at least 2 has domination number at most 2n/5.
Nonblocker
Input: A graph G = (V,E) and an integer k ≥ 0 Question: Does G have a nonblocker of size at least k?
There is a set of 7 graphs with at most 7 vertices that have domination number greater than 2n/5. The following simplification rule for Nonblocker deals with connected components with at most 7 vertices.
Simplification rule 1 (small component). If G has a connected component C with at most 7 vertices, then compute the size of a largest nonblocker of C, remove C from G and decrease k by the size of a largest nonblocker of C.
Observe that the size of a largest nonblocker of C can be computed in O(1) time, since C has O(1) size.
Sometimes our simplification rules for Nonblocker may be able to determine that for some vertex v there is a largest nonblocker that does not contain v. It would be nice to be able to annotate vertices with this information. However, our kernelization algorithm needs to return an instance for Nonblocker, which contains a graph (with no annotations) and an integer. Since such annotations would be lost, Dehne et al. [2] introduce a variant of the problem whith one special vertex that is not allowed to be in the nonblocker. If we had more than one vertex that is not allowed to belong to the nonblocker, we could just merge them into one vertex.
We refer to the vertex c as the catalytic vertex.
Dehne et al. [2] reduce Nonblocker to NBcat by simply adding the catalytic vertex c as an isolated vertex (Catalyzation rule). The instance for NBcat is then preprocessed, making sure to handle all vertices in V \{c} with degree at most 1, and the instance is finally reduced back to an instance for Nonblocker by a De-catalyzation rule. The De-catalyzation rule adds a path on three vertices, makes these three vertices adjacent to c and increases k by 3. The resulting graph has minimum degree at least 2 and the vertices added by the De-catalyzation rule makes sure that c belongs to a largest nonblocker without any need for an annotation. After exhaustively applying Simplification rule 1, Theorem 3 guarantees that the graph has a dominating set of size at most 2n/5, and therefore a nonblocker of size at least 3n/5. Therefore, if k ≤ 3n/5, or, equivalently, if n ≥ 5k/3, then the instance is a Yes-instance, and otherwise the algorithm by Dehne et al. [2] outputs the current instance with less than 5k/3 vertices.
The simplification rules from [2] include the following (they are slightly rephrased):
Simplification rule 2 (isolated vertex). If G contains a vertex v ∈ V \ {c} of degree 0, then remove v from G.
Simplification rule 3 (degree 1). If G contains a vertex v ∈ V \{c} of degree 1 with neighbor u, then set k := k−1, remove v from G, and merge the vertex u into c. In the special case where u = c, the merge operation is void.
Simplification rule 4 (good cut vertex). If G contains a vertex v ∈ V whose neighborhood contains a non-empty subset U ⊆ N(v) such that N(U) = {v} and c ∈/ U, then set k := k − |U|, remove U from G, and merge v into c.
Simplification rule 5 (neighboring non-catalytic degree 2). If G contains neighboring degree-2 vertices u,v ∈ V \ {c} that do not share a common neighbor, then set k := k − 2, merge the two vertices in N ({u, v}), and remove u and v from G. If c was in N({u,v}), then the merged vertex is the new catalytic vertex.
Simplification rule 6 (neighboring catalytic degree 2). If G contains a degree-2 vertex v whose neighborhood N(v) = {c,v′} contains c, then remove the edge vv′ from G.
This results is a 5k/3 + O(1) vertex kernel for Nonblocker, i.e., a kernelization algorithm returning an equiv- alent instance where the graph has at most 5k/3 + O(1) vertices. Here, k refers to the parameter in the original instance. This value of k may increase by up to 3 due to the de-catalyzation rule, leading to an additional constant of at most 5 · 3/3 = 5 in the number of vertices in the kernel beyond 5k/3.
Our improvement to the kernel size will rely on a better bound on the domination number in graphs with minimum degree at least 2 where there are additional restrictions on degree-2 vertices.
Definition 4. A bad cut vertex in a graph G = (V,E) is a vertex x ∈ V such that G − x contains a connected component C that is a cycle on four vertices and x is adjacent to at least one and at most three vertices from C.
Definition 5. A special cycle C in a graph G = (V, E) is a subgraph of G that is a cycle on five vertices such that among every two consecutive vertices on C there is at least one vertex that has degree 2 in G.
Nonblocker with Catalytic Vertex (NBcat)
Input: A graph G = (V, E), a vertex c ∈ V , and an integer k ≥ 0 Question: Does G have a nonblocker S ⊆ V \ {c} of size at least k?
Theorem 6 ([3]). If G = (V,E) is a connected graph on n ≥ 14 vertices with minimum degree at least 2 that 3n
contains no bad cut vertex and no special cycle, then G has domination number at most 8 . 2
3 Exercises
Exercise 1. [30 points] Assume that (G, c, k) is an instance for NBcat such that G has a bad cut vertex x and G − x contains a
connected component C that is a cycle on four vertices and x is adjacent to i vertices from C with 1 ≤ i ≤ 3.
We assume that previously stated simplification rules do not apply (in particular Simplification rule 5 and 6),
so i ≥ 2.
We will have three simplification rules to handle the bad cut vertex x depending on whether the catalytic vertex
belongstoC or{x},namelyforthecaseswherec=x,c∈V(C),andc∈/{x}∪V(C). Show that the following simplification rule is sound.
Simplification rule 7 (cycle-catalytic bad cut). If c ∈ V (C), then
? if c has degree 2 and i = 2, then merge c with one of its neighbors; the merged vertex is the new catalytic
vertex;
? otherwise, if there is a vertex y ∈ V (C) \ (N[c] ∪ N(x)), then merge y into c; ? otherwise, merge x into c.
Exercise 2. [30 points] Based on the statements of the previous exercise, design simplification rules for the cases where x = c and where
c ∈/ {x} ∪ V (C).
Note. If you are asked to design a rule or an algorithm, it is not necessary to prove its correctness or running time. However, in case the rule or algorithm is not correct, it is sometimes difficult to give partial marks if you did not exhibit additional (partially) correct reasoning that led you to the design of the rule or algorithm or that is close to a correctness argument.
Exercise 3. [10 points] Handle special cycles via simplification rules for NBcat.
Exercise 4. [20 points] Argue that Nonblocker has a 8k/5+O(1) vertex kernel based on the work by Dehne et al. [2] and the previous
exercises.
Exercise 5. [10 points]
Design a constant-factor approximation algorithm for Nonblocker.
