Chapter 7: Time Complexity

In a directed graph, the indegreeof a node is the number of incoming edges and the outdegreeis the number of outgoing edges. Show that the following problem is NP-complete. Given an undirected graph G and a designated subset C of G’s nodes, is it possible to convert G to a directed graph by assigning directions to each of its edges so that every node in C has in-degree 0 or outdegree 0, and every other node in G has indegree at least 1?

Is the following formula satisfiable?

$(\mathbf{x}\vee \mathbf{y})\wedge (\mathbf{x}\vee \mathbf{y})\wedge (\mathbf{x}\vee \mathbf{y})\wedge (\mathbf{x}\vee \mathbf{y}).$

Show that$\mathit{P}$ is closed under union, concatenation, and complement.

Show that $\mathit{N}\mathit{P}$is closed under union and concatenation.

Let $\mathbf{CONNECTED}=\{<\mathbf{G}>|\mathbf{G}\mathbf{is}\mathbf{a}\mathbf{connected}\mathbf{undirected}\mathbf{graph}\}.$Analyse the algorithm given on page 185 to show that this language is in .

A triangle in an undirected graph is a $\mathbf{3}-\mathbf{clique}$. Show that$\mathbf{TRIANGLE}\in \mathbf{P}$ , where$\mathbf{TRIANGLE}=\left\{<\mathbf{G}>|\mathbf{G}\mathbf{contains}\mathbf{a}\mathbf{triangle}\right\}.$