Chapter 8: NP-complete problems

In the NODE-DISJOINT PATHS problem, the input is an undirected graph in which some vertices have been specially marked: a certain number of “sources” ${\mathit{s}}_{\mathbf{1}}\mathbf{,}{\mathit{s}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{s}}_{\mathbf{k}}$ and an equal number of “destinations” ${\mathbf{t}}_{\mathbf{1}}\mathbf{,}{\mathbf{t}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathbf{t}}_{\mathbf{k}}$. The goal is to find $\mathbf{k}$ node-disjoint paths (that is, paths which have no nodes in common) where the $\mathbf{i}$th path goes from ${\mathbf{s}}_{\mathbf{i}}$ to ${\mathbf{t}}_{\mathbf{i}}$. Show that this problem is NP-complete.Here is a sequence of progressively stronger hints.

1. Reduce from $\mathbf{3}\mathbf{SAT}$ .
2. For a $\mathbf{3}\mathbf{SAT}$ formula with m clauses and n variables, use $\mathbf{\text{k=m+n}}$ sources and destinations. Introduce one source/destination pair $\left(s_x,t_x\right)$for each variable $\mathbf{x}$ , and one source/destination pair $\left(s_c,t_c\right)$ for each clause $\mathbf{c}$ .
3. For each $\mathbf{3}\mathbf{SAT}$ clause, introducenew intermediate vertices, one for each literal occurring in that clause and one for its complement.

Notice that if the path from ${\mathit{s}}_{\mathbf{c}}$ to ${\mathbf{t}}_{\mathbf{c}}$ goes through some intermediate vertex representing, say, an occurrence of variable $\mathbf{x}$, then no other path can go through that vertex. What vertex would you like the other path to be forced to go through instead?

Proving NP-completeness by generalization. For each of the problems below, prove that it is NP-complete by showing that it is a generalization of some NP-complete problem we have seen in this chapter.

1. SUBGRAPH ISOMORPHISM: Given as input two undirected graphs$\mathbf{G}$ and $\mathbf{H}$, determine whether$\mathbf{G}$ is a subgraph of H (that is, whether by deleting certain vertices and edges of$\mathbf{H}$ we obtain a graph that is, up to renaming of vertices, identical to$\mathbf{G}$ ), and if so, return the corresponding mapping of$\mathbf{V}\mathbf{\left(}\mathbf{G}\mathbf{\right)}$ into$\mathbf{V}\mathbf{\left(}\mathbf{H}\mathbf{\right)}$ .
2. LONGEST PATH: Given a graph role="math" localid="1658141805147" $\mathbf{G}$and an integer$\mathbf{g}$ find in$\mathbf{G}$ a simple path of length$\mathbf{g}$ .
3. MAX SAT: Given a CNF formula and an integer $\mathbf{g}$, find a truth assignment that satisfies at least $\mathbf{g}$clauses.
4. DENSE SUBGRAPH: Given a graph and two integers$\mathbf{a}$ and $\mathbf{b}$, find a set of a vertices of$\mathbf{G}$ such that there are at least$\mathbf{b}$ edges between them.
5. SPARSE SUBGRAPH: Given a graph and two integers$\mathbf{a}$ and$\mathbf{b}$ , find a set of a vertices of$\mathbf{G}$ such that there are at most $\mathbf{b}$edges between them.
6. SET COVER. (This problem generalizes two knownNP-complete problems.)
7. RELIABLE NETWORK: We are given two$\mathbf{n}\mathbf{\times }\mathbf{n}$ matrices, a distance matrix${\mathbf{d}}_{\mathrm{ij}}$ and a connectivity requirement matrix${\mathbf{r}}_{\mathbf{ij}}$ , as well as a budget$\mathbf{b}$ ; we must find a graph $\mathbf{G}\mathbf{=}\mathbf{(}\mathbf{\{}\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{.....}\mathbf{,}\mathbf{n}\mathbf{\}}\mathbf{,}\mathbf{E}\mathbf{)}$such that (1) the total cost of all edges is$\mathbf{b}$ or less and (2) between any two distinct vertices$\mathbf{i}$ and$\mathbf{j}$ there are${\mathbf{r}}_{\mathbf{ij}}$ vertex-disjoint paths.

Determine which of the following problems are NP-complete and which are solvable in polynomial time. In each problem you are given an undirected graph $\mathbf{G}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}\mathbf{E}\mathbf{)}$, along with:

(a)A set of nodes$\mathbf{L}\mathbf{\subseteq }\mathbf{V}$ , and you must find a spanning tree such that its set of leaves includes the set $\mathbf{L}$.

(b)A set of nodes $\mathbf{L}\mathbf{\subseteq }\mathbf{V}$, and you must find a spanning tree such that its set of leaves is precisely the set $\mathbf{L}$.

(c)A set of nodes$\mathbf{L}\mathbf{\subseteq }\mathbf{V}$ , and you must find a spanning tree such that its set of leaves is included in the set $\mathbf{L}$.

(d)An integer $\mathbf{k}$, and you must find a spanning tree with$\mathbf{k}$ or fewer leaves.

(e)An integer $\mathbf{k}$, and you must find a spanning tree with$\mathbf{k}$ or more leaves.

(f)An integer $\mathbf{k}$, and you must find a spanning tree with exactly$\mathbf{k}$ leaves.

Prove that the following problem is NP-complete: given an undirected graph

$G=\left(V,E\right)$and an integer $k$, return a clique of size $k$as well as an independent set of size $k$, provided both exist.

Show that the following problem is NP-complete.

MAXIMUM COMMON SUBGRAPHInput: Two graphs ${\mathbf{G}}_{\mathbf{1}}\mathbf{=}\left(V_1,E_1\right)$and ${\mathbf{G}}_{\mathbf{2}}\mathbf{=}\left(V_2,E_2\right)$; a budget $\mathbf{b}$.Output: Two set of nodes ${{\mathbf{V}}_{\mathbf{1}}}^{\mathbf{\text{'}}}\mathbf{\subseteq }{\mathbf{V}}_{\mathbf{1}}$and ${{\mathbf{V}}_{\mathbf{2}}}^{\mathbf{\text{'}}}\mathbf{\subseteq }{\mathbf{V}}_{\mathbf{2}}$whose deletion leaves at least$\mathbf{b}$ nodes in each graph, and makes the two graphs identical.

We are feeling experimental and want to create a new dish. There are various ingredients we can choose from and we’d like to use as many of them as possible, but some ingredients don’t go well with others. If there arepossible ingredients (numbered $1$to $n$), we write down an matrix giving thediscordbetween any pair of ingredients. Thisdiscordis a real number between $0.0$and $1.0$, where means “they go together perfectly” and $1.0$ means “they really don’t go together.” Here’s an example matrix when there are five possible ingredients.

In this case, ingredients $2$and $3$go together pretty well whereas$1$and$5$clash badly. Notice that this matrix is necessarily symmetric; and that the diagonal entries are always . $0.0$Any set of ingredients incurs apenaltywhich isthe sum of all discord values between pairs of ingredients.For instance, the set of ingredients$\{1,3,5\}$incurs a penalty of $0.2+1.0+0.5=1.7$

.We want this penalty to be small.

EXPERIMENTAL CUISINE

Input:, $n$the number of ingredients to choose from $D$;,the $n\times n$“ discord” matrix; some number$p\ge 0$

OUTPUT:The maximum number of ingredients we can choose with penalty $\le p$.

Show that ifEXPERIMENTAL CUISINEis solvable in polynomial time, then so is 3SAT.

Show that for any problem $\prod _{}$ in NP, there is an algorithm which solves n in time O $\left(2^{p\left(n\right)}\right)$where is the size of the input instance and $\mathit{p}\left(n\right)$is a polynomial (which may depend on$\prod _{}$ ).

Show that if $\mathit{P}\mathbf{=}\mathit{N}\mathit{P}$ then the RSA cryptosystem (Section 1.4.2) can be broken in polynomial time.

Akiteis a graph on an even number of vertices, say 2n, in which of the vertices form a clique and the remaining vertices are connected in a “tail” that consists of a path joined to one of the vertices of the clique. Given a graph and a goal , the KITE problem asks for a subgraph which is a kite and which contains 2g nodes. Prove that KITE is NP-complete.

Optimization versus search.Recall the traveling salesman problem:

TSP

Input: A matrix of distances; a budget b

Output: A tour which passes through all the cities and has $\mathbf{\text{length}}\mathbf{\le }\mathit{b}$, if such a tour exists.

The optimization version of this problem asks directly for the shortest tour.

TSP-OPT

Input:A matrix of distances

Output:The shortest tour which passes through all the cities.

Show that if TSP can be solved in polynomial time, then so can TSP-OPT.