The parameterized complexity landscape of two-sets cut-uncut

DOI10.1016/J.TCS.2025.115726MaRDI QIDQ6864004zbMATH OpenFDO

Authors Matthias Bentert, Fedor V. Fomin, Fanny Hauser, Saket Saurabh

Publication date 4 February 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115726

zbMATH Keywords

fixed-parameter tractabilitypara-NP-hardnesspolynomial kernelsW[1-hardness]XP

Mathematics Subject Classification ID

Connectivity (05C40) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A deterministic almost-linear time algorithm for minimum-cost flow
• A parameterized algorithm for mixed-cut
• A simplified NP-complete satisfiability problem
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
• Computing the largest bond and the maximum connected cut of a graph
• Connecting Terminals and 2-Disjoint Connected Subgraphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Fundamentals of parameterized complexity
• Graph minors. XIII: The disjoint paths problem
• Kernelization Lower Bounds by Cross-Composition
• Maximum independent sets in 3- and 4-regular Hamiltonian graphs
• On partitioning a graph into two connected subgraphs
• Partitioning graphs into connected parts
• Removing local extrema from imprecise terrains
• Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
• Theoretical and computational advances for network diversion
• Two-sets cut-uncut on planar graphs

This page was built for publication: The parameterized complexity landscape of two-sets cut-uncut

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