Matching (multi)cut: algorithms, complexity, and enumeration

DOI10.4230/LIPICS.IPEC.2024.25MaRDI QIDQ7255463zbMATH OpenFDO

Authors Guilherme C. M. Gomes, Emanuel Juliano, Gabriel Martins, Vinícius F. dos Santos

Publication date 29 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2024.25

zbMATH Keywords

enumerationexact exponential algorithmsmatching cutmatching multicutparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cites work

• A new proof and generalizations of a theorem of Erdős and Pósa on graphs withoutk+1 independent circuits
• A note on matching-cut in \(P_t\)-free graphs
• An FPT algorithm for matching cut and d-cut
• Complexity results related to monophonic convexity
• Convex partitions of graphs induced by paths of order three
• Convexity in graphs
• Covering graphs with convex sets and partitioning graphs into convex sets
• Cross-composition: a new technique for kernelization lower bounds
• Cutting Barnette graphs perfectly is hard
• Exact exponential algorithms.
• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
• Finding matching cuts in \(H\)-free graphs
• Finding small separators in linear time via treewidth reduction
• Fundamentals of parameterized complexity
• Good edge-labelling of graphs
• Graph theory
• scientific article; zbMATH DE number 1202982 (Why is no real title available?)
• scientific article; zbMATH DE number 2044946 (Why is no real title available?)
• Irreversible conversion of graphs
• Kernelization. Theory of parameterized preprocessing
• Matching cut in graphs with large minimum degree
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Matching cutsets in graphs
• Matching theory
• Networks immune to isolated line failures
• On Independent Circuits Contained in a Graph
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• On stable cutsets in line graphs
• On structural parameterizations of the matching cut problem
• On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
• Paradigms for parameterized enumeration
• Parameterized algorithms
• Perfect matchings. A theory of matching covered graphs (to appear)
• Randomized Contractions Meet Lean Decompositions
• Recognizing decomposable graphs
• Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
• Short disjoint cycles in graphs with degree constraints
• Some simplified NP-complete graph problems
• The complexity of the matching-cut problem for planar graphs and other graph classes
• The convexity of induced paths of order three and applications: complexity aspects

Cited in

(3)

• Polynomial-size enumeration kernelizations for long path enumeration
• Enumeration kernels for vertex cover and feedback vertex set
• Finding d-cuts in claw-free graphs

This page was built for publication: Matching (multi)cut: algorithms, complexity, and enumeration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7255463)