Strong SDP based bounds on the cutwidth of a graph
From MaRDI portal
Abstract: Given a linear ordering of the vertices of a graph, the cutwidth of a vertex with respect to this ordering is the number of edges from any vertex before (including ) to any vertex after in this ordering. The cutwidth of an ordering is the maximum cutwidth of any vertex with respect to this ordering. We are interested in finding the cutwidth of a graph, that is, the minimum cutwidth over all orderings, which is an NP-hard problem. In order to approximate the cutwidth of a given graph, we present a semidefinite relaxation. We identify several classes of valid inequalities and equalities that we use to strengthen the semidefinite relaxation. These classes are on the one hand the well-known 3-dicycle equations and the triangle inequalities and on the other hand we obtain inequalities from the squared linear ordering polytope and via lifting the linear ordering polytope. The solution of the semidefinite program serves to obtain a lower bound and also to construct a feasible solution and thereby having an upper bound on the cutwidth. In order to evaluate the quality of our bounds, we perform numerical experiments on graphs of different sizes and densities. It turns out that we produce high quality bounds for graphs of medium size independent of their density in reasonable time. Compared to that, obtaining bounds for dense instances of the same quality is out of reach for solvers using integer linear programming techniques.
Cites work
- A branch and bound algorithm for the matrix bandwidth minimization
- A bundle approach for SDPs with exact subgraph constraints
- A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
- A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems
- A note on exact algorithms for vertex ordering problems on graphs
- A polynomial algorithm for the min-cut linear arrangement of trees
- A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
- An experimental comparison of four graph drawing algorithms.
- An SDP-based approach for computing the stability number of a graph
- Antibandwidth and cyclic antibandwidth of meshes and hypercubes
- Branch and bound for the cutwidth minimization problem
- Computational Experience with Stable Set Relaxations
- Computing the cutwidth of bipartite permutation graphs in linear time
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Cutwidth of split graphs and threshold graphs
- Cutwidth of the de Bruijn graph
- Cutwidth: obstructions and algorithmic aspects
- Exact algorithms for the quadratic linear ordering problem
- Graph and string parameters: connections between pathwidth, cutwidth and the locality number
- Graphs with small bandwidth and cutwidth
- Lower bounds for the bandwidth problem
- New exact approaches to row layout problems
- On the hyperbolicity of bipartite graphs and intersection graphs
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
- Partitioning through projections: strong SDP bounds for large graph partition problems
- Semidefinite relaxations of ordering problems
- Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem
- The space of closed subgroups of ℝnis stratified and simply connected
- Tree-width, path-width, and cutwidth
This page was built for publication: Strong SDP based bounds on the cutwidth of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065655)
