# Can the edges of a graph be assigned directions such that all nodes in a given subset have in- or outdegree 0, and every other node indegree > 0?

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

• 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. – Pål GD Apr 19 '13 at 6:28
• See also our reference question. – Raphael Apr 21 '13 at 14:05
• i need more suggestions – kiran Apr 22 '13 at 0:31
• Is this homework? What have you tried, other than posting three versions of the question on this site? – András Salamon Apr 22 '13 at 16:43
• Since finding a graph isomorphism is NP-complete, you could try to reduce your problem to finding a graph isomorphism. – Niklas R. May 1 '13 at 6:58

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.