On the complexity of singly connected vertex deletion

DOI10.1016/J.TCS.2022.08.012MaRDI QIDQ2089067zbMATH OpenOpenAlexFDO

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

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

kernelFPT algorithmtournamentsbounded independence numberlocal tournamentssingly connected digraphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On the Complexity of Singly Connected Vertex Deletion
• A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
• A complexity dichotomy for finding disjoint solutions of vertex deletion problems
• Tight running time lower bounds for vertex deletion problems
• The complexity of some edge deletion problems
• Parameterized complexity of vertex deletion into perfect graph classes
• Parameterized complexity of vertex deletion into perfect graph classes
• On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion
• A parameterized algorithm for bounded-degree vertex deletion
• Vertex deletion problems on chordal graphs

Cites work

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

Cited in

(4)

• Vertex deletion on split graphs: beyond 4-hitting set
• Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
• Addendum to ``An \(O(|V|^{2})\) algorithm for single connectedness
• Make a graph singly connected by edge orientations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2089067)