Max-cut under graph constraints
From MaRDI portal
Abstract: An instance of the graph-constrained max-cut (GCMC) problem consists of (i) an undirected graph G and (ii) edge-weights on a complete undirected graph on the same vertex set. The objective is to find a subset of vertices satisfying some graph-based constraint in G that maximizes the total weight of edges in the cut. The types of graph constraints we can handle include independent set, vertex cover, dominating set and connectivity. Our main results are for the case when G is a graph with bounded treewidth, where we obtain a 0.5-approximation algorithm. Our algorithm uses an LP relaxation based on the Sherali-Adams hierarchy. It can handle any graph constraint for which there is a (certain type of) dynamic program that exactly optimizes linear objectives. Using known decomposition results, these imply essentially the same approximation ratio for GCMC under constraints such as independent set, dominating set and connectivity on a planar graph G (more generally for bounded-genus or excluded-minor graphs).
Recommendations
Cites work
- A 0. 5-approximation algorithm for MAX DICUT with given sizes of parts
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
- scientific article; zbMATH DE number 1342117 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Linear Programming Hierarchies Suffice for Directed Steiner Tree
- Maximizing a monotone submodular function subject to a matroid constraint
- Maximizing nonmonotone submodular functions under matroid or knapsack constraints
- MaxMin allocation via degree lower-bounded arborescences
- Minimum congestion mapping in a cloud
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
- Sparsest cut on bounded treewidth graphs: algorithms and hardness results
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular maximization over multiple matroids via generalized exchange properties
- Tree-width and the Sherali-Adams operator
Cited in
(17)- Node and edge relaxations of the max-cut problem
- Maximum cutwidth problem for graphs.
- Approximating graph-constrained max-cut
- Parameterized complexity of multi-node hubs
- Mixed-integer programming techniques for the connected max-\(k\)-cut problem
- Approximating max-cut under graph-MSO constraints
- On maximum leaf trees and connections to connected maximum cut problems
- From Graph Orientation to the Unweighted Maximum Cut
- Hardness of Graph Pricing Through Generalized Max-Dicut
- \textsc{max-cut} and containment relations in graphs
- scientific article; zbMATH DE number 1404133 (Why is no real title available?)
- Parameterized complexity of multi-node hubs
- A maximum dicut in a digraph induced by a minimal dominating set
- scientific article; zbMATH DE number 7650221 (Why is no real title available?)
- Complexity of the max cut problem with the minimal domination constraint
- Counting connected partitions of graphs
- Canonical dual approach to solving the maximum cut problem
This page was built for publication: Max-cut under graph constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3186491)
