Menger’s Theorem in Temporal Graphs

So. Berman (1996) worked on so called scheduled networks which are multigraphs where every (multi)edge has a start and end time. Meaning, they worked on (un)directed temporal graphs with arbitrarily many labels on each edge with or without travel time specific to each edge (so both strict and nonstrict).

1. Berman showed that the Time-Edge Menger holds via a static expansion
2. he also stated that the traditional Menger-Vertex formulation (with static vertices) does not translate to temporal graphs with an example

Then Kempe, Kleinberg and Kumar (2002) worked on single-labeled temporal networks with strict.

1. KKK cited Berman and claimed that he showed max-flow min-cut with unit capacities — they mean the Menger-Edge
2. KKK then continued to claim that the traditional Menger-Vertex formulation does not translate to temporal graphs (as Berman did) and give a different example than that of Berman
3. they characterized the classes of temporal graphs satisfying the static Menger-Vertex formulation

Lastly, Mertzios, Michail, Spirakis (2013-2018) publish a work on temporal graphs claiming to extend the ‘’single-labeled’’ model of KKK02 and B96. B96 did not work on single-labeled graphs!! They correctly express the results of KKK02, but wrongly associate with B96 only single-labeled, unit capacity max-flow min-cut.

1. MMS18 then show that a temporal Menger-Vertex holds and that this is equivalent to temporal Menger-Edge which was shown by B96.

Notably, MMS18 also used the same static expansion as B96. For more details refer to the Paperlist.

Results

Paperlist

• [Berman 1996] Vulnerability of scheduled networks and a generalization of Menger's Theorem (un)directed, (non)strict, multi-label
• [Kempe, Kleinberg, Kumar 2002] Connectivity and Interference Problems for Temporal Networks undirected, non-strict, simple!
• [George Mertzios, Othon Michail, Paul Spirakis 2013-18] Temporal Network Optimization Subject to Connectivity Constraints (un)directed, strict, multi-label

Questions

• [ ] [ Undirected | Strict ] Maximum Flow: is a normal graph transformation enough or do we need the semaphore construction? → I think the normal is enough?
  • [ ] Prove again that Bermans construction is enough to show Mengers theorem in all setting and that this implies the Max-Flow Min-Cut for SIngle Commodities in all settings

<aside> <img src="/icons/error_red.svg" alt="/icons/error_red.svg" width="40px" />

Mengers Theorem by Berman (and MMS) implies Max-Flow Min-Cut for Single-Commodities

</aside>

• [ ] Write down the proofs for Multi-commodity hardness as sketches at least

<aside> <img src="/icons/error_red.svg" alt="/icons/error_red.svg" width="40px" />

Multi-commodity Flow in Temporal Graphs is NP-complete

</aside>