Hitting Selected (Odd) Cycles

DOI10.1137/15M1041213zbMath1368.05147OpenAlexW2736712640MaRDI QIDQ5348214

Daniel Lokshtanov, Saket Saurabh, Pranabendu Misra, M. S. Ramanujan

Publication date: 14 August 2017

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

Full work available at URL: https://doi.org/10.1137/15m1041213

zbMATH Keywords

parameterized algorithmsodd cycle transversalgraph separation problemsimportant separators sequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Classifying subset feedback vertex set for \(H\)-free graphs ⋮ Deletion to scattered graph classes. I: Case of finite number of graph classes ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ Computing subset transversals in \(H\)-free graphs

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Finding odd cycle transversals.
• Parameterized graph separation problems
• Almost 2-SAT is fixed-parameter tractable
• An improved parameterized algorithm for the minimum node multiway cut problem
• Planar graph bipartization in linear time
• Parametrized complexity theory.
• Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Parameterized Tractability of Multiway Cut with Parity Constraints
• Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
• On Multiway Cut Parameterized above Lower Bounds
• Finding small separators in linear time via treewidth reduction
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Paths, Flowers and Vertex Cover
• Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
• Algorithm Engineering for Optimal Graph Bipartization
• Simpler Parameterized Algorithm for OCT
• Faster Parameterized Algorithms Using Linear Programming
• Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts
• Linear-Time FPT Algorithms via Network Flow
• Multicut is FPT
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Parameterized Algorithms
• Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs

This page was built for publication: Hitting Selected (Odd) Cycles