Vertex splitting #
Splitting the vertices of a directed network turns constraints on vertices into constraints on
arrows. Every vertex v is replaced by an entrance v⁻ = (v, false) and an exit
v⁺ = (v, true) on the vertex type V × Bool. Every original arrow e from v to w is
retained, with its identity, as an arrow from v⁺ to w⁻, and every vertex v, including an
isolated vertex or one carrying loops, receives one split arrow from v⁻ to v⁺. There are no
other arrows; in particular an original loop at v becomes an arrow from v⁺ to v⁻.
Since the only arrow leaving an entrance is its split arrow and every arrow entering an exit is
a split arrow, a walk in the split network starting at an entrance alternates between split
arrows and original arrows. Such walks are therefore exactly the lifts of walks in the original
network: a walk from s to t lifts to a walk from s⁻ to t⁻, or to t⁺ when the split
arrow of t is appended, and projection, which forgets the split arrows, inverts lifting. The
lift of a path is a path, and conversely. A walk starting at an exit s⁺ is a lift with the split
arrow of s removed from the front.
An assignment on the split network consists of an assignment on the original arrows together
with a value on each split arrow. Its excess at v⁻ is the value entering v along original
arrows minus the value on the split arrow of v, and its excess at v⁺ is the value on the
split arrow minus the value leaving v along original arrows. Conservation at both copies of
v therefore says that the value entering v, the value on its split arrow and the value
leaving v all agree, and it implies conservation of the original assignment at v. Since
original conservation alone does not determine the value on the split arrow, both copies are
needed. Under a capacity c v on the split arrow of v, conservation at v⁻ bounds the total
traffic through v by c v; this is how vertex capacities and vertex separators are reduced to
arrow capacities and arrow cuts.
Main definitions #
TauCeti.SplitHom Q: the arrow family of the network obtained fromQby splitting every vertex, with its original arrowsTauCeti.SplitHom.originaland its split arrowsTauCeti.SplitHom.split.TauCeti.ArrowWalk.splitLift: the lift of a walk to the split network.TauCeti.ArrowWalk.splitLiftExit: the lift of a nonempty walk to the split network, starting at the exit of its first vertex.TauCeti.ArrowWalk.splitProj: the projection of a walk in the split network, which forgets its split arrows.TauCeti.ArrowWalk.splitEquiv: lifting identifies the walks fromstotwith the walks in the split network froms⁻to either copy oft.TauCeti.SplitHom.assignment f φ: the split assignment with the values offon original arrows andφ von the split arrow ofv; with capacities forfandφthese are the split capacities.TauCeti.SplitHom.network: the split network, with zero lower bounds and the split capacities as upper bounds.TauCeti.SplitHom.originalAssignment g: the values of a split assignment on original arrows.TauCeti.SplitHom.cutVertices SandTauCeti.SplitHom.cutArrows Q S: the vertices whose split arrows leave a vertex setSof the split network, and the original arrows leavingS.
Main results #
TauCeti.ArrowWalk.isPath_splitLift: lifting preserves and reflects paths.TauCeti.ArrowWalk.isPath_splitProj_of_exit: a walk from an exits⁺projects to a path exactly when it is a path avoidings⁻.TauCeti.ArrowWalk.length_splitLift: a walk withkarrows lifts to a walk with2 * kor2 * k + 1arrows.TauCeti.SplitHom.excessAt_entranceandTauCeti.SplitHom.excessAt_exit: the excesses of a split assignment at the two copies of a vertex.TauCeti.SplitHom.excessAt_originalAssignment: the excess of the original part of a split assignment atvis the sum of its excesses atv⁻andv⁺.TauCeti.SplitHom.excessAt_entrance_eq_zero_and_excessAt_exit_eq_zero_iff: conservation at both copies ofvmeans that the incoming value, the split value and the outgoing value agree.TauCeti.SplitHom.arrowSum_originalAssignment_univ_singleton_leandTauCeti.SplitHom.arrowSum_originalAssignment_singleton_univ_le: a split-arrow capacity bounds the traffic entering and leaving its vertex.TauCeti.SplitHom.arrowSum_assignment_compl: the capacity of a cut of the split network is the capacity of its crossing split arrows plus the capacity of its crossing original arrows.
References #
- L. R. Ford, D. R. Fulkerson, Flows in Networks, Princeton University Press, 1962.
- A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003, Section 9.1.
The arrow family of the network obtained from Q by splitting every vertex v into an
entrance (v, false) and an exit (v, true). The arrows from (v, true) to (w, false) are the
original arrows of Q v w; there is exactly one arrow from (v, false) to (v, true), the split
arrow of v; and there are no other arrows.
Instances For
The lift of a walk from s to t to the split network: it starts at the entrance of s,
crosses the split arrow of every vertex it leaves, and ends at the entrance of t for
b = false and, after crossing the split arrow of t, at the exit of t for b = true.
Instances For
Lifting identifies the walks from s to t with the walks in the split network from the
entrance of s to the entrance (b = false) or exit (b = true) of t; the inverse is
projection.
Instances For
The vertices of the lift ending at an exit: each vertex v of the walk is replaced by its
entrance and its exit.
The vertices of the lift of a nonempty walk ending at an entrance: the vertices of the lift of its prefix ending at an exit, followed by the entrance of its last vertex.
The arrows traversed by the lift ending at an exit: the split arrow of s, followed, for each
arrow of the walk, by that arrow and the split arrow of its target.
The arrows traversed by the lift ending at an entrance: for each arrow of the walk, the split arrow of its source followed by that arrow.
The lift of a walk traverses an original arrow exactly when the walk traverses it.
The lift of a walk ending at an exit traverses the split arrow of v exactly when the walk
visits v.
The lift of a walk ending at an entrance traverses the split arrow of v exactly when the walk
visits v before its last vertex.
Walks starting at an exit #
The lift of the nonempty walk p.cons e from s to x to a walk in the split network
starting at the exit of s: the lift of p.cons e with the split arrow of s removed from the
front. It ends at the entrance of x for b = false and at the exit of x for b = true.
Instances For
The lift of a nonempty walk from the entrance of s is the split arrow of s followed by its
lift from the exit of s.
Projection inverts lifting from the exit.
A walk in the split network from the exit of s whose projection is the nonempty walk
p.cons e is the lift of p.cons e from the exit.
The lift of a path from the exit is a path.
The lift from the exit of a walk p.cons e has 2 * p.length + 1 arrows when it ends at an
entrance and 2 * p.length + 2 arrows when it ends at an exit.
One more than the length of a walk in the split network from the exit of s is twice the
length of its projection, plus one when the walk ends at an exit.
The arrows traversed by a walk in the split network from the exit of s to an exit: for each
arrow of its projection, that arrow and the split arrow of its target.
The arrows traversed by a walk in the split network from the exit of s to an entrance,
preceded by the split arrow of s: for each arrow of its projection, the split arrow of its source
followed by that arrow.
A walk in the split network from the exit of s to an exit traverses the split arrow of v
exactly when its projection visits v after its first vertex.
A walk in the split network from the exit of s to an entrance traverses the split arrow of
v exactly when its projection visits v strictly between its first and last vertices.
Assignments on the split network #
The assignment on the split network with the value f e on each original arrow e and the
value φ v on the split arrow of each vertex v. With capacities cap on the original arrows and
c v on the split arrow of v, the split capacities are assignment cap c.
Instances For
The values of an assignment on the split network on the original arrows.
Instances For
Every assignment on the split network is determined by its values on the original arrows and on the split arrows.
Two assignments on the split network are equal when they agree on the original arrows and on the split arrows.
Split assignments are compared arrowwise on original arrows and vertexwise on split arrows.
The split network: zero lower bounds, the capacity cap e on each original arrow e and the
capacity c v on the split arrow of each vertex v. The body is exposed because the dependent
arrow family occurs in the types of the projection lemmas below.
Instances For
The excess of a split assignment at the entrance (v, false) is the value entering v along
original arrows minus the value on the split arrow of v.
The excess of a split assignment at the exit (v, true) is the value on the split arrow of
v minus the value leaving v along original arrows.
The excess of the original part of a split assignment at v is the sum of its excesses at
the entrance and at the exit of v.
A split assignment is conserved at both copies of v exactly when the value entering v along
original arrows, the value on the split arrow of v and the value leaving v along original
arrows agree.
Conservation of a split assignment at both copies of v implies conservation of its original
part at v.
Vertex capacities. If a split assignment has value at most c on the split arrow of v
and is conserved at the entrance of v, then the total value entering v along original arrows is
at most c.
If a split assignment has value at most c on the split arrow of v and is conserved at the
exit of v, then the total value leaving v along original arrows is at most c.
The vertices whose split arrows leave the vertex set S of the split network: those whose
entrance lies in S and whose exit does not.
Instances For
The original arrows leaving the vertex set S of the split network, each recorded with its
endpoints: the arrows from a vertex whose exit lies in S to a vertex whose entrance does not.
Instances For
Cuts of the split network. The total value of a split assignment on the arrows leaving a
vertex set S is its value on the split arrows leaving S plus its value on the original arrows
leaving S.