Single-exponential FPT algorithms for enumerating secluded F-free subgraphs and deleting to scattered graph classes

DOI10.4230/LIPICS.ISAAC.2023.42MaRDI QIDQ6953175zbMATH OpenFDO

Authors Bart M. P. Jansen, Jari J. H. de Kroon, Michał Włodarczyk

Publication date 24 July 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2023.42

zbMATH Keywords

fixed-parameter tractabilityimportant separatorssecluded subgraphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• 0/1/all CSPs, half-integral A-path packing, and linear-time FPT algorithms
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Almost 2-SAT is fixed-parameter tractable
• An improved parameterized algorithm for the minimum node multiway cut problem
• Clustering with local restrictions
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Covering small independent sets and separators with applications to parameterized algorithms
• Deletion to scattered graph classes. I: Case of finite number of graph classes
• Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
• Designing FPT algorithms for cut problems using randomized contractions
• Directed flow-augmentation
• Discovering archipelagos of tractability for constraint satisfaction and counting
• Finding k-secluded trees faster
• Finding connected secluded subgraphs
• Finding small separators in linear time via treewidth reduction
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• FPT algorithms for path-transversal and cycle-transversal problems
• Half-integrality, LP-branching, and FPT algorithms
• Important separators and parameterized algorithms
• Maximal Flow Through a Network
• Minimum bisection is fixed-parameter tractable
• Multicut Is FPT
• On multiway cut parameterized above lower bounds
• On the computational complexity of length- and neighborhood-constrained path problems
• Parameterized algorithms
• Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
• Parameterized complexity of deletion to scattered graph classes
• Parameterized complexity of secluded connectivity problems
• Parameterized graph separation problems
• Randomized Contractions Meet Lean Decompositions
• Reducing CMSO model checking to highly connected graphs
• Representative sets and irrelevant vertices: new tools for kernelization
• Secluded connectivity problems
• Simple and improved parameterized algorithms for multiterminal cuts
• Solving hard cut problems via flow-augmentation
• The minimum k-way cut of bounded size is fixed-parameter tractable
• The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs

Cited in

(4)

• Preprocessing to reduce the search space for odd cycle transversal
• A polynomial kernel for deletion to the scattered class of cliques and trees
• A polynomial kernel for deletion to the scattered class of cliques and trees
• A parameterized study of secluded structures in directed graphs

This page was built for publication: Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes

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