On the Complexity of Singly Connected Vertex Deletion

DOI10.1007/978-3-030-48966-3_18OpenAlexW3029825649MaRDI QIDQ5041193

Nidhi Purohit, Jayakrishnan Madathil, Lawqueen Kanesh, Avinandan Das, Saket Saurabh, Komal Muluk

Publication date: 13 October 2022

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

Full work available at URL: https://doi.org/10.1007/978-3-030-48966-3_18

zbMATH Keywords

tournamentskernelFPT algorithmbounded independence numberlocal tournamentssingly connected digraphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Related Items

On the complexity of singly connected vertex deletion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Addendum to ``An \(O(|V|^{2})\) algorithm for single connectedness
• Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
• Edge-disjoint paths in digraphs with bounded independence number
• On feedback vertex set: new measure and new structures
• A note on approximation of the vertex cover and feedback vertex set problems -- Unified approach
• Finding odd cycle transversals.
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Improved algorithms for feedback vertex set problems
• A kernelization algorithm for \(d\)-hitting set
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Determining uni-connectivity in directed graphs
• On the feedback vertex set problem in permutation graphs
• An \(O(|V|^2)\) algorithm for single connectedness
• Kernels for deletion to classes of acyclic digraphs
• Polynomial kernels for deletion to classes of acyclic digraphs
• Packing directed circuits fractionally
• Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
• Faster deterministic \textsc{Feedback Vertex Set}
• Wannabe bounded treewidth graphs admit a polynomial kernel for DFVS
• On testing single connectedness in directed graphs and some related problems
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Graph Theory
• A 4 k ² kernel for feedback vertex set
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• Locally Semicomplete Digraphs and Generalizations
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Locally semicomplete digraphs: A generalization of tournaments
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• ON DISJOINT CYCLES
• Classes of Directed Graphs
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Reducibility among Combinatorial Problems
• A naive algorithm for feedback vertex set
• Parameterized and Exact Computation