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$ ?