Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage

DOI10.1007/978-3-031-06678-8_34OpenAlexW4285132620MaRDI QIDQ2169982

Spyridon Tzimas, Charis Papadopoulos

Publication date: 30 August 2022

Full work available at URL: https://arxiv.org/abs/2103.03035

zbMATH Keywords

subset feedback vertex setleafage\( \mathsf{W} \)-hardness

Mathematics Subject Classification ID

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

Related Items (2)

Parameterized complexity of multicut in weighted trees ⋮ A parameterized algorithm for subset feedback vertex set in tournaments

Cites Work

• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Enumerating minimal subset feedback vertex sets
• Finding disjoint paths in split graphs
• The longest path problem has a polynomial solution on interval graphs
• Computing weighted subset transversals in \(H\)-free graphs
• Clustering and domination in perfect graphs
• Intersection graphs of paths in a tree
• Hamiltonian circuits in interval graph generalizations
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• The complexity of generalized clique covering
• Efficient graph representations
• A randomized polynomial kernel for subset feedback vertex set
• A characterisation of rigid circuit graphs
• The separator theorem for rooted directed vertex graphs
• On the tractability of optimization problems on \(H\)-graphs
• Mim-width. II. The feedback vertex set problem
• Intersection graphs of non-crossing paths
• Subset feedback vertex set on graphs of bounded independent set size
• Mim-width. III. Graph powers and generalized distance domination problems
• The vertex leafage of chordal graphs
• Subset feedback vertex sets in chordal graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Polynomial-Time Algorithm for the Leafage of Chordal Graphs
• Node-Deletion Problems on Bipartite Graphs
• Dominating Sets in Chordal Graphs
• The leafage of a chordal graph
• Reducibility among Combinatorial Problems
• Parameterized Algorithms
• Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs
• Computing subset transversals in \(H\)-free graphs
• Subset feedback vertex set in chordal and split graphs
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width

This page was built for publication: Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage