0
$\begingroup$

Let $G$ be a complete directed graph with $n$ vertices. Each vertex $v$ has a weight $w(v)>0$, such that the sum of all vertex weights is $n$. We have that the edge $e$ from $u$ to $v$ has a weight $0 \leq w(e) \leq w(u)$.

We say that these weights can be balanced, if there exists a directed spanning tree, $T$, and function on the edges of $T$, $f$, where $0 \leq f(e)\leq w(e)$, such that for every vertex $v$, we have that $$w(v) + \sum_{e \in I_v} f(e) - \sum_{e \in O_v} f(e)=1$$ where $I_v$ is the set of all edges in $T$ going into $v$, and $O_v$ is the set of edges in $T$ going out from $v$.

Is determining whether the weights can be balanced a known problem? It sounds like a network flow problem, but I'm not too familiar. What's an algorithm which could solve this?

$\endgroup$
  • $\begingroup$ I think something is missing in your condition. $\endgroup$ – Steven Apr 16 at 12:13
  • $\begingroup$ ah yes, my mistake, fixed $\endgroup$ – Zachary Hunter Apr 16 at 17:35
1
$\begingroup$

This solves the problem if the function $f$ is not constrained to the edges of a spanning tree.

You can think of your problem as a flow problem where each vertex $u\in V$ "generates" $w(u)$ units of flow and "sinks" 1 unit of flow.

To reduce this problem to a standard flow formulation you can create a new directed graph $G' = (V', E')$ in which each edge $e \in E'$ has a capacity $c(e)$:

  • $V' = V \cup \{s,t\}$, where $s$ is a new "source" vertex and $t$ is a new "sink" vertex.
  • For each $v \in V$, add to $E'$ the edge $(s,v)$ with capacity $w(u)$.
  • For each edge $e \in E$, add $e$ to $E'$ with capacity $c(e) = w(e)$.
  • For each $v \in V$ add to $E'$ the edge $(v,t)$ with capacity $1$.

Compute the value $f^*$ maximum flow from $s$ to $t$ in $G'$. If $f^* = |V|$ then your all units of flow can be generated and sunk (one unit from each vertex $u \in V$), therefore your problem problem admits a solution. If $f^* < |V|$ your problem admits no solution (to see this you can show that you can convert any feasible solution to your original problem to a flow of $|V|$ in $G'$).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ok, so that's how I would set up the problem. Can you give name of an algorithm to compute maximum flow $f^*$? Sorry, I have not yet learned much about network flow. $\endgroup$ – Zachary Hunter Apr 20 at 17:11
  • $\begingroup$ Also, could you explain why this follows the restrictions that flow must be along a tree? $\endgroup$ – Zachary Hunter Apr 20 at 17:16
  • 1
    $\begingroup$ Uh oh, I'm sorry but I didn't notice the constraint that the flow must move along a spanning tree. For flow algorithms look at Ford-Fulkerson, Edmonds-Karp, and Push-Relabel. $\endgroup$ – Steven Apr 20 at 20:02

Your Answer

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

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