Math Problems Vault

Example 7.36

Does the problem VC remain NP-complete if each edge is to be covered by exactly one vertex?

?

Example 7.37

Prove that MCG is NP-complete.

?

Example 7.38

Partition is NP-complete.

?

Example 7.39

Knapsack is NP-complete.

?

Example 7.40

BP is NP-complete.

?

Example 7.41

Show that the following problem is NP-complete: Given positive integers $a_{1}, \ldots , a_{n}$ , determine whether

\int _{0}^{2 \pi }\left(\prod _{i=1}^{n} \cos \left(a_{i} t\right)\right) d t \neq 0

?

Example 7.42

SMT is NP-complete.

?

Problem 7.4.1

For each of the following problems, determine whether it is $\mathrm{NP}$ -complete or is in $P$ . If it is $\mathrm{NP}$ -complete, find a reduction from a known $\mathrm{NP}$ complete problem to it. If it is in $P$ , find a polynomial-time algorithm for it.

?

(a)

Given a graph $G$ , two vertices $s$ and $t$ in $G$ and a positive integer $k$ , determine whether there is a path between $s$ and $t$ of length less than or equal to $k$ .

(b)

Given a graph $G$ , two vertices $s$ and $t$ in $G$ and a positive integer $k$ , determine whether there is a path between $s$ and $t$ of length greater than or equal to $k$ .

(c)

Given a directed graph $G$ , determine whether $G$ has a cycle of an odd length.

(d)

Given a directed graph $G$ , determine whether $G$ has a cycle of an even length.

(e)

Given a graph $G$ , determine whether $G$ has a cycle of an odd length.

(f)

Given an edge-weighted complete graph $G$ , three subsets $X_{1}, X_{2}$ , $X_{3}$ of vertices and a positive integer $k$ , determine whether there is a subgraph $H$ of $G$ of weight $\leq k$ that contains a spanning tree for each of $X_{1}, X_{2}$ and $X_{3}$ . (A spanning tree for a subset $X \subseteq V$ is a connected subgraph $H$ of $G$ on the vertex set $X$ that has no cycle.)

(g)

Given a graph $G=(V, E)$ and a positive integer $k$ , determine whether there is a subset $T \subseteq E$ of at most $k$ edges such that every vertex in $V$ is incident with at least one edge in $T$ .

(h)

Regular Expression Nonequivalence: Given two regular expressions $r_{1}$ and $r_{2}$ without the Kleene-star operation, determine whether $L\left(r_{1}\right) \neq L\left(r_{2}\right)$ .

(i)

Bounded PCP (see Exercise 7(d) of Section 7.1).

(j)

Bounded Tiling (see Exercise 7(e) of Section 7.1).

Problem 7.4.2

(a)(b)(c)(d)

Prove that the following variations of the problem VC are $\mathrm{NP}$ -complete:

?

(a)

Planar VC: The problem VC restricted to planar graphs. (A planar graph is a graph that can be drawn on the two-dimensional plane such that no two edges cross each other at a non-vertex point.)

(b)

Cubic VC: The problem VC restricted to cubic graphs. (A cubic graph is a graph such that every vertex has degree three.)

(c)

Planar Connected-VC-4: Given a planar graph $G=(V, E)$ with each vertex in $V$ having degree at most 4 and an integer $k>0$ , determine whether there is a vertex cover $C$ of $G$ of size $k$ such that the induced subgraph $\left.G\right|_{C}$ on vertex set $C$ is connected.

(d)

Given a graph $G$ , determine whether $G$ has a vertex cover $C$ satisfying the following conditions:

The subgraph $\left.G\right|_{C}$ induced by $C$ has no isolated point.
Every vertex in $C$ is adjacent to a vertex not in $C$ .

Problem 7.4.3

(a)(b)(c)(d)

The polar representation of a CNF $F$ is a bipartite graph $G_{F}= \left(V_{1}, V_{2}, E\right)$ , where $V_{1}$ is the set of all variables and $V_{2}$ is the set of all clauses in $F$ , and there is an edge in $E$ between $x_{i} \in V_{1}$ and $c_{j} \in V_{2}$ if and only if the variable $x_{i}$ appears in the clause $c_{j}$ (in the form of $x_{i}$ or $\bar{x}_{i}$ ). Prove the following statements:

?

(a)

$(x+y+\bar{z})(\bar{x}+z+w)(\bar{x}+z+\bar{w})(\bar{y}+z+u)(\bar{y}+z+\bar{u})$ has a planar polar representation and it is satisfiable if and only if $x+y=z$ .

(b)

There exists a 3-CNF formula $F$ with a planar polar representation and three variables $x, y$ , and $z$ , such that $F$ is satisfiable if and only if $x y=z$ .

(c)

There exists a 3-CNF formula $F$ with a planar polar representation and three variables $x, y$ , and $z$ , such that $F$ is satisfiable if and only if $x \oplus y=z$ . [Hint: $x \oplus y=x(\bar{x}+\bar{y})+(\bar{x}+\bar{y}) y$ .]

(d)

The following problem, called Planar Polar-3Sat, is NPcomplete: Given a 3-CNF formula $F$ with a planar polar representation, determine whether $F$ is satisfiable or not. [Hint: Applying the fact that $x \oplus (x \oplus y)=y$ and $(x \oplus y) \oplus y=x$ to the construction.]

Problem 7.4.4

(a)(b)

The nonpolar representation of a CNF $F$ is a graph $G_{F}=(V, E)$ , with the vertex set $V$ consisting of all literals and all clauses in $F$ , and the edge set $E$ consisting of all pairs $\left\{ x, \bar{x}\right\}$ over all variables $x$ in $F$ plus all literal-clause pairs $\left\{ z, c\right\}$ such that $z$ occurs in $c$ . Prove the following statements:

?

(a)

If the nonpolar representation of a CNF formula $F$ is planar, then its polar representation must also be planar. However, the converse is not necessarily true.

(b)

The following problem, called Planar Nonpolar-3Sat, is NPcomplete: Given a 3-CNF formula $F$ with a planar nonpolar representation, determine whether $F$ is satisfiable or not.

Problem 7.4.5

(a)(b)(c)

A $(k, \ell )-C N F F$ is a CNF such that each clause contains exactly $k$ literals and each variable occurs in at most $\ell$ clauses. The problem $(k, \ell )$ -Sat is the problem 3SaT restricted to $(k, \ell )$ -CNF's. Prove the following results:

?

(a)

For any $k>0$ , every $(k, k)$ -CNF $F$ is satisfiable.

(b)

For any $\ell >0$ , (2, $\ell$ )-SAT is polynomial-time solvable. (In fact, the problem 2Sat, which is the problem 3Sat restricted to CNF's with at most 2 literals in each clause, is polynomial-time solvable.)

(c)

$(3,4)$ -Sat is $\mathrm{NP}$ -complete.