2
$\begingroup$

Let $G=(V,E)$ be a directed graph. I am interested in a "relaxed" version of the HamCycle problem.

In my first case, the degree of each vertex is exactly 6, such that: 3 are outgoing edges and 3 are ingoing edges, for every vertex in $V$.

I would like to check whether a HamCycle exists in such a graph. I believe it is still NP-Hard, yet not exactly sure on the details. My initial hunch was to perform a reduction from $3SAT$, sort of similar to $HamCycle$, but not exactly sure, since the degree is $6$, each $3$ ingoing and $3$ outgoing, so maybe $3SAT$ wouldn't work.

The second case was when the indegree and outdegree are exactly $2$, but I think it will be clearer after the first case.

$\endgroup$

1 Answer 1

1
$\begingroup$

I believe Hamiltonian Cycle is still NP-hard on graphs where every vertex has in-degree 2 and out-degree 2. Assuming I haven't made a dumb mistake, the standard reduction from 3SAT seems easy to tweak so that it constructs a graph of this property.

Indeed, the standard reduction almost has this property. For each variable, we have a gadget with $3m+3$ nodes, where $m$ counts the number of clauses in the 3CNF formula $\varphi$. Each of those nodes has in-degree 2 and out-degree 2. Then for each clause, we have a node $c$, which has in-degree 1 and out-degree 1, and has a connection from the $i$th node in each gadget and to the $i+1$th node in each gadget. So the only problem are the nodes for the clauses.

We can tweak this to introduce two nodes $c',c''$ for each clause. We have a connection from the $i$th node in each gadget to both $c',c''$; from $c',c''$ to the $i+1$th node; and edges $c\to c'$, $c'\to c$. This ensures that each $c,c'$ have in-degree 2 and out-degree 2. Moreover, you can verify that the reduction still works.

I'll leave it to you to check whether the standard reduction can be tweaked so every node has in-degree 3 and out-degree 3.

Related: Hamiltonian cycle is known to be NP-complete even for $k$-regular graphs, for all $k\ge 3$. See https://cstheory.stackexchange.com/q/1651/5038.

$\endgroup$

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.