Approximating minimum k-section in trees with linear diameter

DOI10.1016/J.ENDM.2015.07.013MaRDI QIDQ324723zbMATH OpenOpenAlexFDO

Authors Cristina G. Fernandes, Tina Janne Schmidt, Anusch Taraz

Publication date 17 October 2016

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

zbMATH Keywords

approximation algorithmminimum \(k\)-section

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Minimum $k$-Section denotes the NP-hard problem to partition the vertex set of a graph into $k$ sets of sizes as equal as possible while minimizing the cut width, which is the number of edges between these sets. When $k$ is an input parameter and $n$ denotes the number of vertices, it is NP-hard to approximate the width of a minimum $k$-section within a factor of $n^c$ for any $c<1$, even when restricted to trees with constant diameter. Here, we show that every tree $T$ allows a $k$-section of width at most $(k-1)(2+16n/diam(T))Delta(T)$. This implies a polynomial-time constant-factor approximation for the Minimum $k$-Section Problem when restricted to trees with linear diameter and constant maximum degree. Moreover, we extend our results from trees to arbitrary graphs with a given tree decomposition.

Recommendations

• Balanced partitions of trees and applications
• On minimum bisection and related partition problems in graphs with bounded tree width
• Balanced partitions of trees and applications
• On minimum bisection and related cut problems in trees and tree-like graphs
• Approximation Algorithms for Min–Max Tree Partition

Cites work

• scientific article; zbMATH DE number 6303002 (Why is no real title available?)
• Balanced graph partitioning
• How Good is Recursive Bisection?
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
• Some simplified NP-complete graph problems

Cited in

(3)

• Minimizing diameters of dynamic trees
• Minimizing the continuous diameter when augmenting a tree with a shortcut
• On minimum bisection and related partition problems in graphs with bounded tree width

This page was built for publication: Approximating minimum \(k\)-section in trees with linear diameter

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