The computational complexity of disconnected cut and \(2 K_2\)-partition

DOI10.1016/j.jctb.2014.09.002zbMath1307.05128OpenAlexW2786954219MaRDI QIDQ2259853

Daniël Paulusma, Barnaby Martin

Publication date: 5 March 2015

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2014.09.002

zbMATH Keywords

disconnected cutbiclique cover\(2K_2\)-partition

Mathematics Subject Classification ID

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) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (19)

Coloring problems on bipartite graphs of small diameter ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Unnamed Item ⋮ Minimal Disconnected Cuts in Planar Graphs ⋮ Disconnected cuts in claw-free graphs ⋮ The complexity of contracting bipartite graphs into small cycles ⋮ Reducing the vertex cover number via edge contractions ⋮ Constraint satisfaction problem: what makes the problem easy ⋮ The Complexity of Boolean Surjective General-Valued CSPs ⋮ Unnamed Item ⋮ A single exponential-time FPT algorithm for cactus contraction ⋮ Parameterizing cut sets in a graph by the number of their components ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Coherent network partitions: characterizations with cographs and prime graphs ⋮ Contracting to a longest path in H-free graphs ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ Surjective \(H\)-colouring: new hardness results ⋮ Coherent network partitions ⋮ The Complexity of Counting Surjective Homomorphisms and Compactions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for partition of some class of graphs under compaction and vertex-compaction
• Increasing the minimum degree of a graph by contractions
• The external constraint 4 nonempty part sandwich problem
• Parameterizing cut sets in a graph by the number of their components
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Edge-contraction problems
• \(2K_{2}\) vertex-set partition into nonempty parts
• Covering graphs with few complete bipartite subgraphs
• Partitioning graphs into connected parts
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• An algorithm for finding clique cut-sets
• On stable cutsets in graphs
• \(2K_2\)-partition of some classes of graphs
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• On disconnected cuts and separators
• Contracting graphs to paths and trees
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• Algorithms for Partition of Some Class of Graphs under Compaction
• Finding Large Clique Minors is Hard
• Recognizing decomposable graphs
• The Complexity of the List Partition Problem for Graphs
• List Partitions
• Compaction, Retraction, and Constraint Satisfaction
• FindingH-partitions efficiently
• Computational Complexity of Compaction to Reflexive Cycles
• Reducibility among Combinatorial Problems
• Fast Skew Partition Recognition
• Classifying the Complexity of Constraints Using Finite Algebras
• Obtaining a Bipartite Graph by Contracting Few Edges

This page was built for publication: The computational complexity of disconnected cut and \(2 K_2\)-partition