CS614. Advanced Algorithms. Exam 1.
CS614. Advanced Algorithms.
Exam 3
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\).
Consider the Dominating Set problem.
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
Can you solve Dominating Set in polynomial time if your input graph does not contain the star \(K_{1,2}\) as an induced subgraph?
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.
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.
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.
Pick any two problems below and show that they are NP-complete.
Given an undirected graph \(G\), does \(G\) contain a simple path that visits all but 9 vertices?
Given an undirected graph \(G\), does \(G\) have a spanning tree in which every node has degree at most 32?
Given an undirected graph \(G\), does \(G\) have a spanning tree with at most 5 leaves?
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\)?