Approximating minimum k-section in trees with linear diameter

DOI10.1016/J.ENDM.2015.07.013zbMATH Open1347.05032arXiv1708.06431OpenAlexW2208485005MaRDI QIDQ324723FDOQ324723

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

Publication date: 17 October 2016

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.

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

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

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)

Cites Work

• Balanced graph partitioning
• Some simplified NP-complete graph problems
• How Good is Recursive Bisection?
• Title not available (Why is that?)
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs

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)