Solving cut-problems in quadratic time for graphs with bounded treewidth

DOI10.1007/978-3-031-23101-8_3MaRDI QIDQ6114456zbMATH OpenOpenAlexFDO

Authors Hauke Brinkop, Klaus Jansen

Publication date 14 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.00694

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: In the problem (Unweighted) Max-Cut we are given a graph $G=(V,E)$ and asked for a set $SsubseteqV$ such that the number of edges from $S$ to $VsetminusS$ is maximal. In this paper we consider an even harder problem: (Weighted) Max-Bisection. Here we are given an undirected graph $G=(V,E)$ and a weight function $wcolonEomathbb{Q}_{>0}$ and the task is to find a set $SsubseteqV$ such that (i) the sum of the weights of edges from $S$ is maximal; and (ii) $S$ contains $leftlceilfracn2ightceil$ vertices (where $n=lvertVvert$). We design a framework that allows to solve this problem in time $mathcalO(2^t{n}^2)$ if a tree decomposition of width $t$ is given as part of the input. This improves the previously best running time for Max-Bisection of [DBLP:journals/tcs/HanakaKS21] by a factor $t^2$. Under common hardness assumptions, neither the dependence on $t$ in the exponent nor the dependence on $n$ can be reduced [DBLP:journals/tcs/HanakaKS21,DBLP:journals/jcss/EibenLM21,DBLP:journals/talg/LokshtanovMS18]. Our framework can be applied to other cut problems like Min-Edge-Expansion, Sparsest-Cut, Densest-Cut, $$-Balanced-Min-Cut, and Min-Bisection. It also works in the setting with arbitrary weights and directed edges.

Recommendations

• A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
• Bisection of bounded treewidth graphs by convolutions
• Bisection of bounded treewidth graphs by convolutions
• On minimum bisection and related partition problems in graphs with bounded tree width
• Graph-Theoretic Concepts in Computer Science

Cites work

• A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Bisection of bounded treewidth graphs by convolutions
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Known algorithms on graphs of bounded treewidth are probably optimal
• On problems equivalent to \((\min,+)\)-convolution
• On the complexity of k-SAT
• On the complexity of finding balanced oneway cuts
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
• Reducibility among combinatorial problems
• The complexity of finding uniform sparsest cuts in various graph classes
• The complexity of satisfiability of small depth circuits
• Treewidth. Computations and approximations

Cited in

(3)

• Bisection of bounded treewidth graphs by convolutions
• Improved parameterized and exact algorithms for cut problems on trees
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs

This page was built for publication: Solving cut-problems in quadratic time for graphs with bounded treewidth

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