Diameters of the Characteristic Imset Polytopes

Abstract

It has been shown that the edge structure of the characteristic imset polytope is closely connected to the question of causal discovery. The diameter of a polytope is an indicator of how connected the polytope is and moreover gives us a hypothetical worst case scenario for an edge-walk over the polytope. We present low-degree polynomial bounds on the diameter of ${\mathrm{CIM}}_n$ and, for any given undirected graph $G$, the face ${\mathrm{CIM}}_G$.

13 pages, 3 figures