1
$\begingroup$

Let be $G=(V,E)$ a directed graph without self loops, where each node has an out-degree of at least $k$.

We want to find a $E'\subset E$, so that $G'=(V,E')$ has the following properties:

  • Almost all nodes in $G'$ have an out-degree of: $l \le k$
  • $G'$ has the highest possible diameter

The almost all nodes part is to relax a bit the problem.

e.g. if $G'$ is a DAG, the last $l$ nodes can't have an out-degree of $l$. But a DAG, or a linear graph, can have a high diameter.

There is also the similar problem, where we want to find $G'$ with the lowest possible diameter.

I have some ideas on how to solve these problems, without finding the optimal solution. In particular the variant max diameter seems doable.

However I'd like to know if there is some literature about these (or similar, or simpler) problems. And if there are algorithms to find optimal or approximated solutions.
I couldn't find anything.

Thanks

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ "Hamiltonian Cycle in a directed graph" is a special case of the (unrelaxed max-diameter) form of the problem: simply set $l=1$. As this is NP-hard, so is your problem. If your relaxation allows 2 outdegree-0 vertices, the problem (with $l=1$ again) is now to look for a Hamiltonian Path (also NP-hard). $\endgroup$ – j_random_hacker Feb 6 '17 at 19:43
  • $\begingroup$ @j_random_hacker Yeah, but this doesn't implies that even the $l>1$ version is NP-hard... (to look for a Hamiltonian Path with $l=1$, should enough a single node with $outdegree=0$) $\endgroup$ – Luca Feb 28 '17 at 9:16
  • $\begingroup$ It's still NP-hard for any given $l > 1$: Reduce from the same problem (HC in a digraph), but construct the input instance for your problem differently: instead of just using the same graph $G$, add a complete directed graph on $l$ vertices $u_1, \dots, u_l$ to it, and add $n(l-1)$ edges from every $v \in V$ to the first $l-1$ of these new vertices (i.e., add the edge $(v_i, u_j)$ for all $1 \le i \le n$ and $1 \le j \le l-1$). There's a subgraph $H$ of this graph that (a) has every vertex of outdegree $l$ and (b) contains a shortest path of length $n-1$ iff there is a HC in $G$. $\endgroup$ – j_random_hacker Mar 1 '17 at 10:55
  • $\begingroup$ Also I didn't understand the part of your comment in parentheses... $\endgroup$ – j_random_hacker Mar 1 '17 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.