Speaker: Jane Coons, WPI
Title: The Degree-Bounded Characteristic Imset Polytope
Abstract: The characteristic imset (CIM) polytope is a 0/1 polytope whose vertices represent Markov equivalence classes of directed acyclic graphs. Several causal discovery problems can be viewed as solving a linear program over the CIM polytope. However, since the dimension of the CIM polytope grows exponentially in the number of nodes of the underlying DAG, solving these linear programs is computationally intractable. We introduce the degree-bounded characteristic imset polytope, whose vertices correspond only to DAGs whose nodes have bounded in-degree k. For fixed k, the dimension of this polytope grows polynomially in the number of nodes of the DAG. For k=1, we show that this polytope is a matroid independence polytope and we give an extensive list of facets for this polytope when k=2.