Algorithms for partitioning weighted trees without conflicting terminals
Algorithms for Connected Multicuts of Weighted Trees
Data Structures and Algorithms
Summary
This research looks at ways to cut up a weighted tree structure into connected parts, each containing certain important points called terminals, while avoiding pairs of points that conflict with each other. The goal is to split the tree so that the cost of cutting edges is minimized in two different ways. The authors provide approximate and exact algorithms for these problems, especially when the conflict patterns among terminals have specific structures. They also introduce a new way to measure conflict complexity, broadening previous methods.
What this means in practice
- •For network designers: Design communication or transportation networks partitioned to avoid conflicting node pairs while controlling maximum edge cut cost per region.
- •For graph algorithm developers: Create specialized algorithms that optimally separate trees with structured conflicts, improving multicut solutions when conflict patterns meet certain complexity conditions.
Authors
Sunny Atalig, Marek Chrobak, Petr Kolman, Claire Mathieu, Hans Raj Tiwary
Abstract
In the \emph{connected multicut problem for weighted trees}, the instance is an edge-weighted tree $T = (V,E,ω)$, a set of terminals $Γ\subseteq V$, and a set of pairwise ``conflicts'' between these terminals represented by edges of a conflict graph $\mathcal{C} = (Γ,\mathcal{F})$. A \emph{connected multicut} for this instance is a partition $\mathcal{M}$ of the vertex set $V$ into subsets called the \emph{components of $\mathcal{M}$}, where each component induces a subtree of $T$, contains at least one terminal, but does not contain any conflicting terminal pair. Two cost functions for multicuts are considered: in the min-sum variant, we minimize the total weight of the edges between different components of $\mathcal{M}$, and in the min-max variant, we minimize the maximum, over all components, of the total weight of edges leaving the component. In the first part of the paper, we focus on algorithms for the min-max variant, for which we give a $2$-approximation algorithm for the unweighted case, a $(2+ε)$-approximation algorithm for the general case, and a mildly exponential exact algorithm for the unweighted case. In the second part of the paper, we study algorithms that take advantage of the structure of the conflict graph. We first give a polynomial-time exact algorithm for the min-max variant when $\mathcal{C}$ is a clique (the variant referred to in the literature as the \emph{multiway cut}). Next, we generalize this result by providing polynomial-time exact algorithms, for both variants, for instances whose conflict graph has constant \emph{split complexity} --- a new parameter that refines the concept of neighborhood diversity previously studied in the context of parameterized complexity. This unifies and generalizes previous results for the min-sum variant when conflict graphs are complete multipartite graphs or unions of cliques.