Two Hardness Results on Feedback Vertex Sets
From MaRDI portal
Publication:3004674
DOI10.1007/978-3-642-21204-8_26zbMath1329.68125OpenAlexW157976967MaRDI QIDQ3004674
Wei Jiang, Tian Liu, Tienan Ren, Ke Xu
Publication date: 3 June 2011
Published in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-21204-8_26
Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Counting independent sets and maximal independent sets in some subclasses of bipartite graphs ⋮ Circular convex bipartite graphs: feedback vertex sets ⋮ Union Closed Tree Convex Sets ⋮ Total vertex-edge domination in graphs: Complexity and algorithms ⋮ Performances of pure random walk algorithms on constraint satisfaction problems with growing domains ⋮ Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ Counting dominating sets in some subclasses of bipartite graphs ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ On convexity in split graphs: complexity of Steiner tree and domination ⋮ Cosecure domination: hardness results and algorithms ⋮ Some new algorithmic results on co-secure domination in graphs ⋮ Complete Boolean satisfiability solving algorithms based on local search ⋮ The complexity of secure domination problem in graphs ⋮ Fractional Edge Cover Number of Model RB ⋮ Maximum Edge Bicliques in Tree Convex Bipartite Graphs ⋮ Algorithmic aspects of certified domination in graphs ⋮ Counting independent sets in tree convex bipartite graphs ⋮ Algorithmic aspects of secure connected domination in graphs ⋮ Algorithmic aspects of 2-secure domination in graphs ⋮ Large hypertree width for sparse random hypergraphs ⋮ Circular Convex Bipartite Graphs: Feedback Vertex Set ⋮ Tractable connected domination for restricted bipartite graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- Feedback vertex set in hypercubes
- On the independence number of random graphs
- Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies
- Improved algorithms for feedback vertex set problems
- Improved approximation algorithm for the feedback set problem in a bipartite tournament
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- Minimum weight feedback vertex sets in circle graphs
- An efficient algorithm for minimum feedback vertex sets in rotator graphs
- Minimum feedback vertex sets in shuffle-based interconnection networks
- Random constraint satisfaction: easy generation of hard (satisfiable) instances
- Feedback vertex sets in star graphs
- Almost exact minimum feedback vertex set in meshes and butterflies
- New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
- Many hard examples in exact phase transitions
- An Approximation Algorithm for Feedback Vertex Sets in Tournaments
- Finding Induced Subgraphs via Minimal Triangulations
- A fixed-parameter algorithm for the directed feedback vertex set problem
- On Feedback Vertex Set New Measure and New Structures
- Feedback Vertex Sets in Rotator Graphs
- Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments
- A Graph Theoretic Approach to Statistical Data Security
- Node-Deletion Problems on Bipartite Graphs
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Tractable Feedback Vertex Sets in Restricted Bipartite Graphs
- Probability and Computing
- Random Graphs
- A Min-Max Theorem on Feedback Vertex Sets
