Abstract
The acyclic subgraph problem can be formulated as follows. Given a digraph with arc weights, find a set of arcs containing no directed cycle and having maximum total weight. We investigate this problem from a polyhedral point of view and determine several classes of facets for the associated acyclic subgraph polytope. We also show that the separation problem for the facet defining dicycle inequalities can be solved in polynomial time. This implies that the acyclic subgraph problem can be solved in polynomial time for weakly acyclic digraphs. This generalizes a result of Lucchesi for planar digraphs.
Similar content being viewed by others
References
M.R. Garey and D.S. Johnson,Computers and intractability: A guide to the theory of NP-completeness (Freeman, San Francisco, 1979).
M. Grötschel, M. Jünger and G. Reinelt, “Facets of the linear ordering polytope”, this volume, pp. xx–yy.
M. Grötschel, M. Jünger and G. Reinelt, “A cutting plane algorithm for the linear ordering problem”,Operations Research 32 (1984) 1195–1220.
M. Grötschel, M. Jünger and G. Reinelt, “Optimal triangulation of large real-world input-outputmatrices”,Statistische Hefte 25 (1984) 261–295.
M. Grötschel, L. Lovász and A. Schrijver, “The ellipsoid method and its consequences in combinatorial optimization”,Combinatorica 1 (1981) 169–197.
R. Kaas, “A branch and bound algorithm for the acyclic subgraph problem”,European Journal of Operational Research 8 (1981) 355–362.
C.L. Lucchesi, “A minimax equality for directed graphs”, Doctoral Thesis, University of Waterloo (Waterloo, Ontario, 1976).
C.L. Lucchesi and D.H. Younger, “A minimax relation for directed graphs”,Journal of the London Mathematical Society (2) 17 (1978) 369–374.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Grötschel, M., Jünger, M. & Reinelt, G. On the acyclic subgraph polytope. Mathematical Programming 33, 28–42 (1985). https://doi.org/10.1007/BF01582009
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582009