Groupe d’études et de recherche en analyse des décisions

G-2005-57

Polyhedra for the Equivalent Subgraph Problem

We give some properties of the equivalent subgraph polytope and its dominant. We characterize those digraphs whose corresponding polyhedra are completely described by bound and trivial dicut inequalities. We give complete descriptions of the equivalent subgraph polyhedra for a class of digraphs which includes directed Halin graphs. As well we derive the description of the dominant of the dicut polytope and we show that the equivalent subgraph problem is polynomially solvable for this class.

, 24 pages