In a directed graph, the indegree of a node is the number of incoming edges and the outdegree is 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 indegree 0 or outdegree 0, and every other node in G has indegree at least 1?

I need an idea how to prove it

  • 6
    $\begingroup$ What have you tried? Did you try to reduce from 3SAT? Perhaps let the vertices in $C$ be variables and the vertices in $V \setminus C$ be clauses? Then the clause vertices have indegree at least one if and only if they are satisfied by a variable vertex? Remember that you also must prove that it is in NP, but that should be a walk in the park. $\endgroup$ Commented Apr 19, 2013 at 6:28
  • 1
    $\begingroup$ See also our reference question. $\endgroup$
    – Raphael
    Commented Apr 21, 2013 at 14:05
  • $\begingroup$ i need more suggestions $\endgroup$
    – kiran
    Commented Apr 22, 2013 at 0:31
  • 1
    $\begingroup$ Is this homework? What have you tried, other than posting three versions of the question on this site? $\endgroup$ Commented Apr 22, 2013 at 16:43
  • $\begingroup$ Since finding a graph isomorphism is NP-complete, you could try to reduce your problem to finding a graph isomorphism. $\endgroup$ Commented May 1, 2013 at 6:58

3 Answers 3


take $C=\emptyset$ then you want to direct the graph so all node have in degree at least 1($DA1$) and now think about directed Hamiltonian cycle($DHC$) how you can reduce $DHC$ to $DA1$ !


Hint: Each edge has two possible orientations in the result. So you can encode this decision with a propositional variable. Next, encode your requirements for nodes in $C$ and outside $C$ as clauses. How many clauses do you need for that?


Our problem is $NP$-complete by a reduction from $3SAT$.

For each literal either positive or negative, create a vertex for it.

Set $C$ to be the set of literals themselves.

For each pair of literals of the same variable $x_i$, namely $x_i$ and $\lnot x_i$, connect them by an edge. This ensures that whenever $x_i$ is assigned to $\mathrm{TRUE}$ (all outgoing arcs) then $\lnot x_i$ is assigned to $\mathrm{FALSE}$ (all incoming arcs), and vice versa whenever $\lnot x_i$ is assigned to $\mathrm{TRUE}$ (all outgoing) then $x_i$ is assigned to $\mathrm{FALSE}$ (all incoming). Hence, make sure the assignment is consistent.

Now, we take care of the clauses.

For each clause, create for it a new vertex. Connect this new clause-vertex to its $3$ literal-vertices in $C$. And so, we are done.

A satisfying assignment exists if and only the produced undirected graph can be oriented such that each vertex in $C$ is either a source vertex, i.e. $\mathrm{TRUE}$ with all outgoing arcs, or a sink vertex, i.e. $\mathrm{FALSE}$ with all incoming arcs. A clause-vertex needs to have at least one satisfying literal which is witnessed by the direction of an incoming arc. DONE.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.