# trekSeparation -- trek separation statements of a mixed graph

## Synopsis

• Usage:
trekSeparation(G)
• Inputs:
• G, an instance of the type MixedGraph, mixed graph with directed and bidirected edges
• Outputs:
• a list, of lists \{A,B,CA,CB\}, where (CA,CB) trek-separates A from B

## Description

A trek between vertices $i$ and $j$ in a mixed graph $G$ with directed and bidirected edges is a triple $(P_L,P_R)$ where $P_L$ is a directed path of directed edges with sink $i$ and source $k$, $P_R$ is a directed path of directed edges with sink $j$ and source $l$, and either $k=l$ or there is a bidirected edge between $k$ and $l$. Let $A,B,CA,CB$ be subsets of vertices of $G$.

We say that $(CA,CB)$ trek-separates $A$ from $B$ in $G$ if for every trek $(P_L,P_R)$ from a vertex in $A$ to a vertex in $B$, either $P_L$ contains a vertex in $CA$ or $P_R$ contains a vertex in $CB$.

The function trekSeparation returns a list of trek separation statements $\{A,B,CA,CB\}$\,where $#CA + #CB < min(#A, #B)$. Each statement is maximal in the ordering where $\{A1,B1,CA,CB\}\,<\,\{A2,B2,CA,CB\}$\,if $A1$ is a subset of $A2$ and $B1$ is a subset of $B2$. Each statement is also unique up to symmetry, since $\{B,A,CB,CA\}$\,is a trek separation statement if and only if $\{A,B,CA,CB\}$.

 i1 : G = mixedGraph(digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}}) o1 = MixedGraph{Bigraph => Bigraph{a => {d}} } d => {a} Digraph => Digraph{b => {c, d}} c => {d} d => {} Graph => Graph{} o1 : MixedGraph i2 : S = trekSeparation G o2 = {{{a}, {b, c}, {}, {}}, {{a, b}, {b, c}, {}, {b}}, {{b, c}, {a, b}, {}, ------------------------------------------------------------------------ {b}}, {{b, c}, {a, c}, {}, {c}}, {{b, c}, {d, a}, {}, {d}}} o2 : List

## Caveat

trekSeparation $G$ is only implemented for mixedGraphs with directed and bidirected edges.