Subset feedback vertex set in chordal and split graphs

DOI10.1007/978-3-030-17402-6_30zbMath1429.68198arXiv1901.02209OpenAlexW2963978247WikidataQ127781153 ScholiaQ127781153MaRDI QIDQ5919404

Geevarghese Philip, Prafullkumar Tale, Varun Rajan, Saket Saurabh

Publication date: 6 February 2020

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1901.02209

zbMATH Keywords

chordal graphssplit graphsparameterized complexitysubset feedback vertex set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (6)

Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ A parameterized algorithm for subset feedback vertex set in tournaments ⋮ Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs ⋮ Exact algorithms for restricted subset feedback vertex set in chordal and split graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Subset feedback vertex set on graphs of bounded independent set size

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Enumerating minimal subset feedback vertex sets
• Exact exponential algorithms.
• A kernelization algorithm for \(d\)-hitting set
• The splittance of a graph
• A randomized polynomial kernel for subset feedback vertex set
• Algorithmic graph theory and perfect graphs
• Faster exact algorithms for some terminal set problems
• Subset feedback vertex sets in chordal graphs
• Hitting Forbidden Minors: Approximation and Kernelization
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Linear Time Parameterized Algorithms for S <scp>ubset</scp> F <scp>eedback</scp> V <scp>ertex</scp> S <scp>et</scp>
• Subquadratic Kernels for Implicit 3-H <scp>itting</scp> S <scp>et</scp> and 3-S <scp>et</scp> P <scp>acking</scp> Problems
• Kernelization
• Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Exact Algorithms via Monotone Local Search
• Half-integrality, LP-branching and FPT Algorithms
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Parameterized Algorithms

This page was built for publication: Subset feedback vertex set in chordal and split graphs