1. Homepage
  2. Homework
  3. COMP6741: Algorithms for Intractable Problems - Assignment 2: Nonblocker
This question has been solved

COMP6741: Algorithms for Intractable Problems - Assignment 2: Nonblocker

Contact Us On WeChat
AustraliaUNSWCOMP6741Algorithms for Intractable ProblemsNonblocker

Assignment 2
COMP6741: Algorithms for Intractable Problems

Name: insert your name here
Student number: insert your student number here CourseNana.COM

1 Instructions CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

2 Background CourseNana.COM

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 CourseNana.COM

vV\ShasaneighborinS.AsubsetofverticesSV isanonblockerofGifV\SisadominatingsetofG. Example: CourseNana.COM

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 CourseNana.COM

de transitioning via one edge to a state that is not in S. f CourseNana.COM

Let us now define the Nonblocker problem. CourseNana.COM

The current smallest kernel for Nonblocker relies heavily on an upper bound on the domination number of graphs of minimum degree at least 2. CourseNana.COM

Definition 2. The domination number of a graph G is the size of a smallest dominating set of G. CourseNana.COM

Theorem 3 ([1, 4]). Every connected graph on n 8 vertices with minimum degree at least 2 has domination number at most 2n/5. CourseNana.COM

Nonblocker CourseNana.COM

Input: A graph G = (V,E) and an integer k 0 Question: Does G have a nonblocker of size at least k? CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

Observe that the size of a largest nonblocker of C can be computed in O(1) time, since C has O(1) size. CourseNana.COM

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. CourseNana.COM

We refer to the vertex c as the catalytic vertex. CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

Simplification rule 3 (degree 1). If G contains a vertex v V \{c} of degree 1 with neighbor u, then set k := k1, remove v from G, and merge the vertex u into c. In the special case where u = c, the merge operation is void. CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

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 vvfrom G. CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

Nonblocker with Catalytic Vertex (NBcat) CourseNana.COM

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? CourseNana.COM

Theorem 6 ([3]). If G = (V,E) is a connected graph on n 14 vertices with minimum degree at least 2 that 3n CourseNana.COM

contains no bad cut vertex and no special cycle, then G has domination number at most 8 . 2 CourseNana.COM

3 Exercises CourseNana.COM

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 CourseNana.COM

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 CourseNana.COM

belongstoC or{x},namelyforthecaseswherec=x,cV(C),andc/{x}∪V(C). Show that the following simplification rule is sound. CourseNana.COM

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 CourseNana.COM

? otherwise, if there is a vertex y V (C) \ (N[c] N(x)), then merge y into c; ? otherwise, merge x into c. CourseNana.COM

Exercise 2. [30 points] Based on the statements of the previous exercise, design simplification rules for the cases where x = c and where CourseNana.COM

c / {x} ∪ V (C). CourseNana.COM

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. CourseNana.COM

Exercise 3. [10 points] Handle special cycles via simplification rules for NBcat. CourseNana.COM

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 CourseNana.COM

Exercise 5. [10 points] CourseNana.COM

Design a constant-factor approximation algorithm for Nonblocker. CourseNana.COM


Get Expert Help On This Assignment

Scan above qrcode with Wechat

Australia代写,UNSW代写,COMP6741代写,Algorithms for Intractable Problems代写,Nonblocker代写,Australia代编,UNSW代编,COMP6741代编,Algorithms for Intractable Problems代编,Nonblocker代编,Australia代考,UNSW代考,COMP6741代考,Algorithms for Intractable Problems代考,Nonblocker代考,Australiahelp,UNSWhelp,COMP6741help,Algorithms for Intractable Problemshelp,Nonblockerhelp,Australia作业代写,UNSW作业代写,COMP6741作业代写,Algorithms for Intractable Problems作业代写,Nonblocker作业代写,Australia编程代写,UNSW编程代写,COMP6741编程代写,Algorithms for Intractable Problems编程代写,Nonblocker编程代写,Australiaprogramming help,UNSWprogramming help,COMP6741programming help,Algorithms for Intractable Problemsprogramming help,Nonblockerprogramming help,Australiaassignment help,UNSWassignment help,COMP6741assignment help,Algorithms for Intractable Problemsassignment help,Nonblockerassignment help,Australiasolution,UNSWsolution,COMP6741solution,Algorithms for Intractable Problemssolution,Nonblockersolution,