On the complexity of singly connected vertex deletion

DOI10.1016/j.tcs.2022.08.012OpenAlexW4293700582MaRDI QIDQ2089067

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

Publication date: 6 October 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.08.012

zbMATH Keywords

tournamentskernelFPT algorithmbounded independence numberlocal tournamentssingly connected digraphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Make a graph singly connected by edge orientations

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• A partial k-arboretum of graphs with bounded treewidth
• 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
• 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
• On the Complexity of Singly Connected Vertex Deletion
• A naive algorithm for feedback vertex set
• Parameterized and Exact Computation
• Parameterized Algorithms
• Digraphs

This page was built for publication: On the complexity of singly connected vertex deletion