# The two paths problem and theorem

{pause up}
## Two paths problem

{pause .block title="Two paths problem" #probleme-deux-chemins}
> Given four vertices $s_1,s_2,t_1,t_2$ in a graph, find two vertex-disjoint paths, from $s_1$ to $t_1$ and from $s_2$ to $t_2$, respectively.
>
> {carousel #deux-chemins-probleme}
> ----
> > ![](dessins/deux-chemins-probleme-graphe.svg)
> ---
> > ![](dessins/deux-chemins-probleme-chemins.svg)

{change-page="deux-chemins-probleme"}

{change-page="deux-chemins-probleme"}

{pause up ="probleme-deux-chemins" carousel #deux-chemins-exemples}
----
> ![](dessins/exemple-deux-chemins.svg)
---
> ![](dessins/exemple-deux-chemins-arete.svg)
---
> ![](dessins/contre-exemple-deux-chemins.svg)

{change-page="deux-chemins-exemples"}

{change-page="deux-chemins-exemples"}

{pause up="deux-chemins-exemples"}
- Many algorithms exist.

{pause}
- The first "efficient" algorithm [Shiloach, 1980] is in $O(nm)$.

{pause}
- The most efficient known algorithm is linear [Kawarabayashi, Li, Reed, 2015].

{pause}
- All assume finding all the cutvertices, $2$-separators as a first step.

{pause}
- The difficulty is then to find other reductions (e.g. particular $3$-separators, a planarity test, compaction algorithms, etc).

{pause}
**We provide a $O(nm)$ algorithm made of two simple procedures:**

{pause}
- **The only external calls are to simple search algorithms.**

{pause}
- **Each procedure takes $\sim 10$ lines of pseudo-code.**

{pause}
- **Finding separators is not necessary.**

{pause up}
## Two paths theorem

{pause #cross-cycle}
Generalisation from $s_1,s_2,t_1,t_2$ to a cycle $C$:

{pause carousel #deux-chemins-cycle}
----
> ![](dessins/deux-chemins-cycle-graphe.svg)
---
> ![](dessins/deux-chemins-cycle-cycle.svg)
---
> ![](dessins/deux-chemins-cycle-mauvais.svg)
---
> ![](dessins/deux-chemins-cycle-barre.svg)
---
> ![](dessins/deux-chemins-cycle-final.svg)

{change-page="deux-chemins-cycle"}

{change-page="deux-chemins-cycle"}

{change-page="deux-chemins-cycle"}

{change-page="deux-chemins-cycle"}

{pause}
Such a pair of vertex-disjoint paths is called a **$C$-crossing**.

{pause .definition #definition-toile}
A **web** is a planar graph whose triangles are all inner faces and whose inner faces are all triangles, with a cycle for the unbounded face.
[An **hyper-web** is an hypergraph obtained by replacing the triangles of a web with $3$-edges.]{pause}

{pause carousel #hypertoiles up="deux-chemins-cycle"}
----
> ![](dessins/hypertoile-toile-1.svg)
---
> ![](dessins/hypertoile-1.svg)
---
> ![](dessins/hypertoile-toile-2.svg)
---
> ![](dessins/hypertoile-2.svg)

{change-page="hypertoiles"}

{change-page="hypertoiles" up="definition-toile"}

{change-page="hypertoiles"}

{pause}
The external cycle $C$ of a (hyper)web is called its **frame**.

{pause #shape}
**Shape**: $G$ can be obtained by substituting the hyperedges of the shape by graphs.

{pause}
> {carousel #representations-abstraites-graphes}
> ----
> > ![](dessins/representations-abstraites-graphes-1.svg)
> ---
> > ![](dessins/representations-abstraites-graphes-2.svg)
> ---
> > ![](dessins/representations-abstraites-graphes-3.svg)
>
> {change-page="representations-abstraites-graphes"}
>
> {change-page="representations-abstraites-graphes"}

{pause .theorem #theoreme-deux-chemins title="Two paths theorem" up="shape"}
> Let $G$ be a graph and $C$ a cycle on $G$'s vertices. Either $G$ contains a $C$-crossing, or $G$ has the shape of an hyperweb with frame $C$.
>
> {pause up="definition-toile"}
>
> {pause up="shape"}
>
> {pause}
> Furthermore, with $C$ the frame of an hyperweb $H$, {pause}
> - there is no $C$-crossing in $H$, {pause}
> - if $u$ and $v$ are two non-adjactent vertices of $H$, then $H+uv$ contains a $C$-crossing.

{pause up="theoreme-deux-chemins"}
There exists several proof for equivalent variants of this theorem:

{pause}
- All use Menger's theorem. [Some use Kuratowski's theorem.]{pause}

{pause}
- All assume first to reduce to the $3$-connected case.

{pause}
- Some do not mention the maximality part.

{pause}
- The first generalisation from $s_1,s_2,t_1,t_2$ to a cycle is found in [Robertson and Seymour, 1990] in the form of **societies**.

{pause}
**We provide a new proof for the two paths theorem:**

{pause}
- **It avoids Menger's and Kuratowski's theorem.**

{pause}
- **It avoids connectivity reductions.**