CS614. Advanced Algorithms. Exam 1.

CS614. Advanced Algorithms.

Exam 3

EXACT MATCH (3 points)

Given a graph G and an integer k, the EXACT MATCH problem asks for an induced matching of size k, that is, k edges x_1 y_1, \ldots, x_k y_k such that the 2k endpoints are all distinct and there is no edge between \left\{x_i, y_i\right\} and \left\{x_j, y_j\right\} for any i \neq j.

Prove that EXACT MATCH parameterized by k is as hard as INDEPENDENT SET parameterized by k.

Dominating Set on Restricted Classes

Consider the Dominating Set problem.

Problem 2.1 Understanding graph classes (1 point)

Let \mathcal{A} be the graphs excluding the star K_{1,4} as an induced subgraph. That is, a graph G belongs to \mathcal{A} if and only if there is no copy of a star on four leaves as an induced subgraph (but you may still have vertices of degree four or more).

Similarly, let \mathcal{B} be the graphs excluding the star K_{1,2} as an induced subgraph.

Which of the following is true?

\mathcal{A} \subseteq \mathcal{B}
\mathcal{B} \subseteq \mathcal{A}
neither of the above

Problem 2.2 An Easy Case (2 points)

Can you solve Dominating Set in polynomial time if your input graph does not contain the star K_{1,2} as an induced subgraph?

Problem 2.3 A Hard Case (4 points)

Prove that Dominating Set restricted to graphs excluding the star K_{1,4} as an induced subgraph is as hard as Dominating Set on general graphs.

Hint: look up the textbook (Theorem 13.15) reduction for Connected Dominating Set and adapt it.

PERMUTATION COMPOSITION (3 points)

The EXACT UNIQUE HITTING SET problem is the following:

Input: A universe U, a set A of subsets of U, and an integer k. Question: Does there exist a set X \subseteq U of size exactly k such that |A \cap X|=1 for every A \in A?

In the PERMUTATION COMPOSITION problem, the input consists of a family \mathcal{P} of permutations of a finite universe U, additional permutation \pi of U, and an integer k, and the question is whether one can find a sequence \pi_1, \pi_2, \ldots, \pi_k \in \mathcal{P} such that:

\pi=\pi_1 \circ \pi_2 \circ \ldots \circ \pi_k.

Show a reduction from EXACT UNIQUE HITTING SET to PERMUTATION COMPOSITION.

NICE SUBSET (3 points)

Let G=\left(X, Y, E\right) be an undirected bipartite graph, that is, a graph whose nodes are divided into two sets, X and Y, such that every edge in E connects a node in X to a node in Y. The nodes in X are all labeled with non-negative integers.

Some of the nodes in Y can be removed to leave a subset W \subseteq Y. A subset W is called nice with G if every node in X which has been assigned a number m is connected to exactly m nodes in W. An example of a nice set is in the image below.

The problem is to determine whether a nice W exists. Demonstrate a reduction from 3SAT to this problem.

NP-completeness Examples (4 points)

Pick any two problems below and show that they are NP-complete.

Problem 5.1

Given an undirected graph G, does G contain a simple path that visits all but 9 vertices?

Problem 5.2

Given an undirected graph G, does G have a spanning tree in which every node has degree at most 32?

Problem 5.3

Given an undirected graph G, does G have a spanning tree with at most 5 leaves?

Problem 5.4

Given an undirected graph G=(V, E), what is the size of the largest subset of vertices S \subseteq V such that at most 50 edges in E have both endpoints in S?