Compositions in the bipartite subgraph polytope

DOI10.1016/0012-365X(92)90133-ZMaRDI QIDQ1199475zbMATH OpenOpenAlexFDO

Authors Jean Fonlupt, A. R. Mahjoub, Jean-Pierre Uhry

Publication date 16 January 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(92)90133-z

zbMATH Keywords

bipartite subgraph polytopeedge weightsmax-cut problempolynomial time algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (05C99) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Analysis of algorithms and problem complexity (68Q25)

Review text

Given a graph \(G=(V,E)\) with edge weights \(c(e)>0\) for all \(e\in E\), the max-cut problem (the problem of finding a cut with maximal weight) is equivalent to the following linear problem \(\text{Max}\{cx;x\in P_ B(G)\}\), where \(P_ B(G)\) is the bipartite subgraph polytope of \(G\), defined as the convex hull of the incidence vectors of all edge sets of bipartite subgraphs of \(G\). (For \(F\subseteq E\) the incidence vector \(x^ F\in\mathbb{R}^{| E|}\) is defined by \(x^ F(e)=1\) if \(e\in F\) and \(x^ F(e)=0\) if \(e\notin F.)\) The max-cut problem and the related bipartite subgraph polytope are studied in graphs which are decomposable by clique-articulation having at most three vertices. If \(G\) decomposes into \(G_ 1,\dots,G_ n\) it is shown that there exists a polynomial time algorithm to solve the max-cut problem in \(G\) provided that such an algorithm is known for appropriate graphs defined from \(G_ 1,\dots,G_ n\). If \(G\) decomposes into \(G_ 1\) and \(G_ 2\), a linear system of inequalities is derived which defines the bipartite subgraph polytope of \(G\) from two linear systems related to \(G_ 1\) and \(G_ 2\). Using this result, it is shown that if \(G_ 1\) and \(G_ 2\) are weakly bipartite graphs then \(G\) is weakly bipartite. Moreover, it is proved that every graph noncontractible to \(K_ 5\) is weakly bipartite. Further classes of weakly bipartite graphs are discussed.

Recommendations

• scientific article; zbMATH DE number 780784
• The Maximum Induced Bipartite Subgraph Problem with Edge Weights
• Small bipartite subgraph polytopes
• Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
• Facets of the Bipartite Subgraph Polytope

Cites work

• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Binary group and Chinese postman polyhedra
• Clique-Web Facets for Multicut Polytopes
• Compositions in the bipartite subgraph polytope
• Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
• Compositions of Graphs and Polyhedra II: Stable Sets
• Experiments in quadratic 0-1 programming
• Facets for the cut cone. I
• Facets for the cut cone. II: Clique-web inequalities
• Facets of the Bipartite Subgraph Polytope
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 17640 (Why is no real title available?)
• scientific article; zbMATH DE number 3311627 (Why is no real title available?)
• Matroids and multicommodity flows
• Node-and edge-deletion NP-complete problems
• On some weakly bipartite graphs
• On the cut polytope
• Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
• The ellipsoid method and its consequences in combinatorial optimization
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Weakly bipartite graphs and the max-cut problem
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(22)

• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• On a composition of independence systems by circuit identification
• Compositions in the bipartite subgraph polytope
• Facets for the cut cone. I
• Laplacian eigenvalues and the maximum cut problem
• One-node cutsets and the dominating set polytope
• The maximum cardinality cut problem in co-bipartite chain graphs
• On graphs of the cone decompositions for the min-cut and max-cut problems
• Composition of graphs and the triangle-free subgraph polytope
• A characterization of weakly bipartite graphs
• Applications of cut polyhedra. II
• Polyhedral results for the bipartite induced subgraph problem
• Composition of graphs and the triangle free subgraph polytope
• The Maximum Induced Bipartite Subgraph Problem with Edge Weights
• Facets of the Bipartite Subgraph Polytope
• Solving VLSI design and DNA sequencing problems using bipartization of graphs
• Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
• Approximating unique games using low diameter graph decomposition
• Small bipartite subgraph polytopes
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• On cuts and matchings in planar graphs
• Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem

This page was built for publication: Compositions in the bipartite subgraph polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199475)