2
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 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$
    – Pål GD
    Apr 19, 2013 at 6:28
  • 1
    $\begingroup$ See also our reference question. $\endgroup$
    – Raphael ♦
    Apr 21, 2013 at 14:05
  • $\begingroup$ i need more suggestions $\endgroup$
    – kiran
    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$
    – András Salamon
    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$
    – Niklas Rosencrantz
    May 1, 2013 at 6:58

3 Answers 3

Reset to default
1
$\begingroup$

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$ !

Improve this answer
$\endgroup$
0
$\begingroup$

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?

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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