Compositions of Graphs and Polyhedra IV: Acyclic Spanning Subgraphs
Barahona, Francisco; Fonlupt, Jean; Mahjoub, Ali Ridha (1994), Compositions of Graphs and Polyhedra IV: Acyclic Spanning Subgraphs, SIAM Journal on Discrete Mathematics, 7, 3, p. 390-402. http://dx.doi.org/10.1137/S0895480190182691
Type
Article accepté pour publication ou publiéDate
1994Nom de la revue
SIAM Journal on Discrete MathematicsVolume
7Numéro
3Éditeur
SIAM
Pages
390-402
Identifiant publication
Métadonnées
Afficher la notice complèteRésumé (EN)
Given a directed graph $D$ that has a two-vertex cut, this paper describes a technique to derive a linear system that defines the acyclic subgraph polytope of $D$ from systems related to the pieces. It also gives a technique to describe facets of this polytope by composition of facets for the pieces. The authors prove that, if the systems for the pieces are totally dual integral (TDI), then the system for $D$ is also. The authors prove that the "cycle inequalities" form a TDI system for any orientation of $K_5$. These results are combined with Lucchesi–Younger theorem and a theorem of Wagner to prove that, for graphs with no $K_{3,3} $ minor, the cycle inequalities characterize the acyclic subgraph polytope and form a TDI system. This shows that, for this class of graphs, the cardinality of a minimum feedback set is equal to the maximum number of arc disjoint cycles. For planar graphs, this is a consequence of the Lucchesi–Younger theorem.Mots-clés
Polytope; acyclic subgraphs; composition of polyhedra; Polyhedral combinatoricsPublications associées
Affichage des éléments liés par titre et auteur.
-
Barahona, Francisco; Mahjoub, Ali Ridha (1994) Article accepté pour publication ou publié
-
Barahona, Francisco; Mahjoub, Ali Ridha (1994) Article accepté pour publication ou publié
-
Barahona, Francisco; Mahjoub, Ali Ridha (1994) Article accepté pour publication ou publié
-
Bendali, Fatiha; Mailfert, Jean; Mahjoub, Ali Ridha (2002) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha (1994) Article accepté pour publication ou publié