Back to Search
Start Over
A (probably) optimal algorithm for Bisection on bounded-treewidth graphs
- Publication Year :
- 2020
-
Abstract
- The maximum/minimum bisection problems are, given an edge-weighted graph, to find a bipartition of the vertex set into two sets whose sizes differ by at most one, such that the total weight of edges between the two sets is maximized/minimized. Although these two problems are known to be NP-hard, there is an efficient algorithm for bounded-treewidth graphs. In particular, Jansen et al. (SIAM J. Comput. 2005) gave an $O(2^tn^3)$-time algorithm when given a tree decomposition of width $t$ of the input graph, where $n$ is the number of vertices of the input graph. Eiben et al. (ESA 2019) improved the dependency of $n$ in the running time by giving an $O(8^tt^5n^2\log n)$-time algorithm. Moreover, they showed that there is no $O(n^{2-\varepsilon})$-time algorithm for trees under some reasonable complexity assumption. In this paper, we show an $O(2^t(tn)^2)$-time algorithm for both problems, which is asymptotically tight to their conditional lower bound. We also show that the exponential dependency of the treewidth is asymptotically optimal under the Strong Exponential Time Hypothesis. Finally, we discuss the (in)tractability of both problems with respect to special graph classes.<br />13 pages, 2 figures
- Subjects :
- FOS: Computer and information sciences
Exponential time hypothesis
General Computer Science
Upper and lower bounds
Tree decomposition
Theoretical Computer Science
Vertex (geometry)
Exponential function
Treewidth
Asymptotically optimal algorithm
Bounded function
Computer Science - Data Structures and Algorithms
Data Structures and Algorithms (cs.DS)
Algorithm
Mathematics
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....b019000852e5370f4c6bf4936a43dafb