Solving Partition Problems Almost Always Requires Pushing Many Vertices Around

DOI10.1137/19M1239362zbMath1434.05123MaRDI QIDQ5220192

Manuel Sorge, Christian Komusiewicz, Erik Jan van Leeuwen, Iyad A. Kanj

Publication date: 11 March 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

graph partitioningpolynomial kernelmonopolar graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Cluster deletion on interval graphs and split related graphs

Uses Software

• Stony Brook

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization
• More about subcolorings
• The complexity of partitioning into disjoint cliques and a triangle-free graph
• Algorithms for unipolar and generalized split graphs
• Solving partition problems with colour-bipartitions
• On the parameterized complexity of multiple-interval graph problems
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• The complexity of \(G\)-free colourability
• Subcolorings and the subchromatic number of a graph
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Recognition of unipolar and generalised split graphs
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• Partitioning a graph into disjoint cliques and a triangle-free graph
• Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
• Complexity and algorithms for recognizing polar and monopolar graphs
• Parametrized complexity theory.
• Graph Theory
• On the computational complexity of (O,P)-partition problems
• Graph Subcolorings: Complexity and Algorithms
• Parameterized Algorithms on Perfect Graphs for Deletion to (r,l)-Graphs
• Kernelization
• Kernelization Lower Bounds by Cross-Composition
• A Polynomial Kernel for Proper Interval Vertex Deletion
• On the Polarity and Monopolarity of Graphs
• On 2-Subcolourings of Chordal Graphs
• Parameterized Algorithms