The Complexity of Tree Partitioning
- PDF / 6,733,988 Bytes
- 38 Pages / 439.37 x 666.142 pts Page_size
- 25 Downloads / 249 Views
The Complexity of Tree Partitioning Zhao An1 · Qilong Feng1 · Iyad Kanj2 · Ge Xia3 Received: 8 May 2018 / Accepted: 14 March 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Given a tree T on n vertices, and k, b, s1 , … , sb ∈ ℕ , the Tree Partitioning problem asks if at most k edges can be removed from T so that the resulting components can be grouped into b groups such that the number of vertices in group i is si , for i = 1, … , b . The case where s1 = ⋯ = sb = n∕b , referred to as the Balanced Tree Partitioning problem, was shown to be NP -complete for trees of maximum degree at most 5, and the complexity of the problem for trees of maximum degree 4 and 3 was posed as an open question. The parameterized complexity of Balanced Tree Partitioning was also posed as an open question in another work. In this paper, we answer both open questions negatively. We show that Balanced Tree Partitioning (and hence, Tree Partitioning) is NP -complete for trees of maximum degree 3, thus closing the door on the complexity of Balanced Tree Partitioning, as the simple case when T is a path is in P . In terms of the parameterized complexity of the problems, we show that both Balanced Tree Partitioning and Tree Partitioning are W[1]-complete parameterized by k. Using a compact representation of the solution space for an instance of the problem, we present a dynamic programming algorithm for the weighted version of Tree Partitioning (and hence for that of Bal√ anced Tree Partitioning) that runs in subexponential-time 2O( n) , adding a natural problem to the list of problems that can be solved in subexponential time. Finally, we extend this subexponential-time algorithm to the Weighted Graph Partitioning problem on graphs of treewidth o(n∕ lg n) , and we also show an application of this subexponential-time algorithm for approximating the Weighted Graph Partitioning problem. Keywords Tree partitioning · Parameterized complexity · Subexponential-time algorithms
A preliminary version of the paper appeared in Proceedings of the 15th International Symposium on Algorithms and Data Structures (WADS), volume 10389 of Lecture Notes in Computer Science. Springer, 2017. Extended author information available on the last page of the article
13
Vol.:(0123456789)
Algorithmica
1 Introduction 1.1 Problem Definition and Motivation We consider the Tree Partitioning problem defined as follows: Tree Partitioning Given: A tree T; k, b, s1 , … , sb ∈ ℕ Parameter: k Question: Does there exist a subset E� ⊆ E(T) of at most k edges such that the components of T − E� can be grouped into b groups, where group i contains si vertices, for i ∈ [b]? The special case of the problem when s1 = ⋯ = sb = |V(T)|∕b (i.e., when all the groups have the same size) is referred to as Balanced Tree Partitioning.1 The two problems are special cases of the Balanced Graph Partitioning problem, which has applications in the areas of parallel computing [2], computer vision [2], VLSI circuit design [3], route planning [11], and image pr
Data Loading...
