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