Skip to main content
4 of 4
fixed typo
Elle Najt
  • 1.5k
  • 2
  • 11
  • 13

Reference on the faces of the circulation polytope

On page 4 of Generating all vertices of a polyhedron is hard it is mentioned that the facial structure of the circulation polyhedron* is well understood. I am trying to find a reference for this.

I know how to show that the vertices correspond to directed simple cycles, but I am looking for a combinatorial description of the higher dimensional faces of this polyhedron in terms of the underlying graph. In particular, when are two vertices adjacent?

Edit : I think that the face lattice embeds in $\{0,1\}^A$ via the support of a vector function ($x \in P$ goes to $\{ i : x_i > 0\}$), and this makes the face lattice isomorphic to the lattice of directed subgraphs of $G$ that are unions of directed simple cycles. This is pretty much the description I'm looking for, although based on the link it seems like more is probably known in the right references -- if I can verify the details I'll update the question with an answer.

*The circulation polyhedron of a directed graph $(G,A)$ is defined by:

$\{ x \in \mathbb{R}^E : x \geq 0, \nabla \cdot x = 0 \}$, where $\nabla : \mathbb{R}^E \to \mathbb{R}^V$ is the "graph divergence" operator, $(\nabla \cdot e)(v) =\sum_{ (i,v) | (i,v) \in E} x_{(i,v)} - \sum_{ (v,i) \in E} x_{(v,i)}$.

Elle Najt
  • 1.5k
  • 2
  • 11
  • 13