Approximating graph-constrained max-cut

• 成果类型: Article
• 署名作者: Shen, Xiangkun; Lee, Jon; Nagarajan, Viswanath
• 署名单位: University of Michigan System; University of Michigan
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1154-3
• 发表日期: 2018
• 页码: 35-58
• 关键词: algorithms; maximization; sizes

摘要

An instance of the graph-constrained max-cut ( GCMC) problem consists of ( i) an undirected graphG = ( V, E) and ( ii) edge-weights c : V 2 . R+ on a complete undirected graph. The objective is to find a subset S. V of vertices satisfying some graph-based constraint in G that maximizes the weight u. S, v/. S cuv of edges in the cut ( S, V \ S). 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 1 2 -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 dynamic program of a specific form. Using known decomposition results, these imply essentially the same approximation ratio forGCMCunder constraints such as independent set, dominating set and connectivity on a planar graph G.