Question

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?

Short answer

The problem is NP-complete by a reduction from 3 SAT. Yes, it is possible to convert G.

Step-by-step solution

Step-1: Indegree and outdegree nodes

In a network, in-degree nodes refer to the number of incoming edges, whereas out-degree nodes refer to the number of existing edges.

Step-2: To Reduct the SAT Problem

Yes if G is oriented in such a way that every node in C has an indegree or outdegree of 0 and every node in V\C has a positive indegree, otherwise No.

By a reduction from 3 SAT, the problem is NP-complete. For each literal, a vertex is formed.

Let's call the set of literals set C.

Each pair of literals, $x_i$as well as $\neg x_i$, should be connected with the edge.

As a result, whenever $x_i$is set to True, $\neg x_i$is set to False, and vice versa. As a result, the task is constant. For each clause, a new vertex is produced.

In C, the new clause vertex is linked to its three literal vertices. If an undirected network is generated with C's every vertex being either a source vertex(True) with outgoing arcs or a sink vertex(false) with incoming arcs, a satisfying assignment exists.