On the parameterized complexity of computing balanced partitions in graphs
From MaRDI portal
(Redirected from Publication:493645)
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.
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
Cites work
- scientific article; zbMATH DE number 4131663 (Why is no real title available?)
- scientific article; zbMATH DE number 4215390 (Why is no real title available?)
- scientific article; zbMATH DE number 5485537 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1953101 (Why is no real title available?)
- scientific article; zbMATH DE number 2044928 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A \(c^k n\) 5-approximation algorithm for treewidth
- A framework for solving VLSI graph layout problems
- A scalable multi-level preconditioner for matrix-free µ-finite element analysis of human bone structures
- Algorithmic lower bounds for problems parameterized by clique-width
- An \(\mathcal{O}(n^4)\) time algorithm to compute the bisection width of solid grid graphs
- Applications of a Planar Separator Theorem
- Balanced graph partitioning
- Balanced partitions of trees and applications
- Bin packing with fixed number of bins revisited
- Cluster vertex deletion: a parameterization between vertex cover and clique-width
- Exact combinatorial branch-and-bound for graph bisection
- Expanding the expressive power of monadic second-order logic on restricted graph classes
- Fast balanced partitioning is hard even on grids and trees
- Fibonacci heaps and their uses in improved network optimization algorithms
- Finding small separators in linear time via treewidth reduction
- Fundamentals of parameterized complexity
- Graph theory
- Graph-Theoretic Concepts in Computer Science
- Improved upper bounds for vertex cover
- Kernelization Lower Bounds by Cross-Composition
- Kernelization: new upper and lower bound techniques
- Minimum bisection is fixed parameter tractable
- On the parameterized complexity of computing graph bisections
- On the parameterized complexity of multiple-interval graph problems
- Parameterized graph separation problems
- Parametrized complexity theory.
- Partitioning Planar Graphs
- Some simplified NP-complete graph problems
- The treewidth and pathwidth of hypercubes
- Treewidth. Computations and approximations
- Upper bounds to the clique width of graphs
- Vertex Bisection is Hard, too
- What makes equitable connected partition easy
Cited in
(7)- Approximation and parameterized algorithms for balanced connected partition problems
- The parameterized complexity of the minimum shared edges problem
- On the parameterized complexity of computing graph bisections
- Minimum Bisection Is Fixed-Parameter Tractable
- On minimum vertex bisection of random \(d\)-regular graphs
- Balanced Judicious Bipartition is Fixed-Parameter Tractable
- Approximation algorithms for maximally balanced connected graph partition
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)
