Computing subset vertex covers in H-free graphs

DOI10.1016/J.TCS.2025.115088MaRDI QIDQ7021855zbMATH OpenFDO

Authors Nick Brettell, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Johannes Rauch, Erik Jan van Leeuwen

Publication date 26 February 2025

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

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115088

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• Bounding the mim‐width of hereditary graph classes
• Chordal probe graphs
• Classifying subset feedback vertex set for H-free graphs
• Computing and Combinatorics
• Computing subset transversals in \(H\)-free graphs
• Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs
• Enumerating minimal subset feedback vertex sets
• Face covers and the genus problem for apex graphs
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• From matchings to independent sets
• Graph classes with structured neighborhoods and algorithmic applications
• Graph theory with applications
• Graphen und Matrices.
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• Independent set on P_k-free graphs in quasi-polynomial time
• Line Graphs of Helly Hypergraphs
• Maximum regular induced subgraphs in 2P₃-free graphs
• Maximum weight independent set for claw-free graphs in polynomial time
• Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• On graphs with polynomially solvable maximum-weight clique problem
• On line graphs of subcubic triangle-free graphs
• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs
• Quasi-polynomial-time algorithm for independent set in P_t-free graphs via shrinking the space of induced paths
• Subset feedback vertex set on graphs of bounded independent set size
• The strong perfect graph theorem
• Upper bounds to the clique width of graphs

Cited in

(2)

• Finding d-cuts in probe H-free graphs
• Subset feedback vertex set and subset vertex cover on AT-free graphs

This page was built for publication: Computing subset vertex covers in \(H\)-free graphs

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