On the complexity of singly connected vertex deletion
type: Item
instance of: scholarly article
title: On the complexity of singly connected vertex deletion
author: Avinandan Das
author: Lawqueen Kanesh
author: Jayakrishnan Madathil
author: Komal Muluk
author: Nidhi Purohit
author: Saket Saurabh
published in: Theoretical Computer Science
publication date: 2022-10-06T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7597110
zbMATH Keywords: singly connected digraphs
zbMATH Keywords: FPT algorithm
zbMATH Keywords: kernel
zbMATH Keywords: bounded independence number
zbMATH Keywords: tournaments
zbMATH Keywords: local tournaments
MaRDI profile type: Publication
full work available at URL: j.tcs.2022.08.012
OpenAlex ID: W4293700582
cites work: A kernelization algorithm for \(d\)-hitting set
cites work: Kernels for deletion to classes of acyclic digraphs
cites work: A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
cites work: Locally semicomplete digraphs: A generalization of tournaments
cites work: Locally Semicomplete Digraphs and Generalizations
cites work: Digraphs
cites work: Classes of Directed Graphs
cites work: Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
cites work: Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
cites work: Q5111250
cites work: ON DISJOINT CYCLES
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Determining uni-connectivity in directed graphs
cites work: Q4313087
cites work: A naive algorithm for feedback vertex set
cites work: On feedback vertex set: new measure and new structures
cites work: Improved algorithms for feedback vertex set problems
cites work: A fixed-parameter algorithm for the directed feedback vertex set problem
cites work: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
cites work: Parameterized Algorithms
cites work: On the Complexity of Singly Connected Vertex Deletion
cites work: An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
cites work: On testing single connectedness in directed graphs and some related problems
cites work: Q4027320
cites work: Fixed-Parameter Tractability and Completeness I: Basic Results
cites work: Edge-disjoint paths in digraphs with bounded independence number
cites work: A note on approximation of the vertex cover and feedback vertex set problems -- Unified approach
cites work: Q3283482
cites work: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
cites work: Parameterized and Exact Computation
cites work: Reducibility among Combinatorial Problems
cites work: An \(O(|V|^2)\) algorithm for single connectedness
cites work: Addendum to ``An \(O(|V|^{2})\) algorithm for single connectedness''
cites work: Faster deterministic \textsc{Feedback Vertex Set}
cites work: Q4952178
cites work: On the feedback vertex set problem in permutation graphs
cites work: Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
cites work: Wannabe bounded treewidth graphs admit a polynomial kernel for DFVS
cites work: Polynomial kernels for deletion to classes of acyclic digraphs
cites work: Faster fixed parameter tractable algorithms for finding feedback vertex sets
cites work: Finding odd cycle transversals.
cites work: Packing directed circuits fractionally
cites work: A 4 k 2 kernel for feedback vertex set
DOI: 10.1016/J.TCS.2022.08.012
Recommended article: On the Complexity of Singly Connected Vertex Deletion
Recommended article: A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
Recommended article: Tight Running Time Lower Bounds for Vertex Deletion Problems
Recommended article: The complexity of some edge deletion problems
Recommended article: Parameterized Complexity of Vertex Deletion into Perfect Graph Classes
Recommended article: Parameterized complexity of vertex deletion into perfect graph classes
Recommended article: On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion
Recommended article: A Parameterized Algorithm for Bounded-Degree Vertex Deletion
Recommended article: Vertex deletion problems on chordal graphs
description: scientific article; zbMATH DE number 7597110