On the parameterized complexity of computing balanced partitions in graphs
From MaRDI portal
Publication:493645
DOI10.1007/S00224-014-9557-5zbMATH Open1329.68150arXiv1312.7014OpenAlexW2032278054MaRDI QIDQ493645FDOQ493645
Authors: René van Bevern, Andreas Emil Feldmann, Manuel Sorge, Ondřej Suchý 
Publication date: 4 September 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Abstract: A balanced partition is a clustering of a graph into a given number of equal-sized parts. For instance, the Bisection problem asks to remove at most k edges in order to partition the vertices into two equal-sized parts. We prove that Bisection is FPT for the distance to constant cliquewidth if we are given the deletion set. This implies FPT algorithms for some well-studied parameters such as cluster vertex deletion number and feedback vertex set. However, we show that Bisection does not admit polynomial-size kernels for these parameters. For the Vertex Bisection problem, vertices need to be removed in order to obtain two equal-sized parts. We show that this problem is FPT for the number of removed vertices k if the solution cuts the graph into a constant number c of connected components. The latter condition is unavoidable, since we also prove that Vertex Bisection is W[1]-hard w.r.t. (k,c). Our algorithms for finding bisections can easily be adapted to finding partitions into d equal-sized parts, which entails additional running time factors of n^{O(d)}. We show that a substantial speed-up is unlikely since the corresponding task is W[1]-hard w.r.t. d, even on forests of maximum degree two. We can, however, show that it is FPT for the vertex cover number.
Full work available at URL: https://arxiv.org/abs/1312.7014
Recommendations
- Balanced connected partitions of graphs: approximation, parameterization and lower bounds
- Approximation and parameterized algorithms for balanced connected partition problems
- Approximation algorithms for maximally balanced connected graph partition
- Approximation algorithms for maximally balanced connected graph partition
- Sparse balanced partitions and the complexity of subgraph problems
- Approximating the Maximally Balanced Connected Partition Problem in graphs
- scientific article; zbMATH DE number 2058980
- Balanced graph partitioning
- Parameterized algorithms for graph partitioning problems
- Parameterized algorithms for graph partitioning problems
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Graph theory
- Fundamentals of parameterized complexity
- Title not available (Why is that?)
- Fibonacci heaps and their uses in improved network optimization algorithms
- Applications of a Planar Separator Theorem
- Balanced graph partitioning
- Upper bounds to the clique width of graphs
- Parametrized complexity theory.
- Title not available (Why is that?)
- Parameterized graph separation problems
- Some simplified NP-complete graph problems
- Kernelization Lower Bounds by Cross-Composition
- Improved upper bounds for vertex cover
- Treewidth. Computations and approximations
- Cluster vertex deletion: a parameterization between vertex cover and clique-width
- On the parameterized complexity of multiple-interval graph problems
- Finding small separators in linear time via treewidth reduction
- Title not available (Why is that?)
- Algorithmic lower bounds for problems parameterized by clique-width
- Title not available (Why is that?)
- A scalable multi-level preconditioner for matrix-free µ-finite element analysis of human bone structures
- A framework for solving VLSI graph layout problems
- Bin packing with fixed number of bins revisited
- Kernelization: new upper and lower bound techniques
- Balanced partitions of trees and applications
- An \(\mathcal{O}(n^4)\) time algorithm to compute the bisection width of solid grid graphs
- Fast balanced partitioning is hard even on grids and trees
- The treewidth and pathwidth of hypercubes
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph-Theoretic Concepts in Computer Science
- A \(c^k n\) 5-approximation algorithm for treewidth
- On the parameterized complexity of computing graph bisections
- Expanding the expressive power of monadic second-order logic on restricted graph classes
- Vertex Bisection is Hard, too
- Title not available (Why is that?)
- What makes equitable connected partition easy
- Partitioning Planar Graphs
- Exact combinatorial branch-and-bound for graph bisection
- Minimum bisection is fixed parameter tractable
Cited In (9)
- The parameterized complexity of the minimum shared edges problem
- On the parameterized complexity of computing graph bisections
- On minimum vertex bisection of random \(d\)-regular graphs
- Balanced Judicious Bipartition is Fixed-Parameter Tractable
- The complexity of tree partitioning
- Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity
- Approximation algorithms for maximally balanced connected graph partition
- Approximation and parameterized algorithms for balanced connected partition problems
- Minimum Bisection Is Fixed-Parameter Tractable
Uses Software
This page was built for publication: On the parameterized complexity of computing balanced partitions in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q493645)
