arXiv preprint ·
Algorithms for Connected Multicuts of Weighted Trees
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Near-Linear Time Maximum Clique in Circular Arc Graphs
No Escape from the Quadratic Barrier: Adaptive Attacks on Linear $\ell_2$ Sketches
Computing faster with a full memory: Catalytic algorithms break time-space lower bounds
Approximating Independent Sets Using Additive Combinatorics
Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.