Reducing graph transversals via edge contractions

DOI10.1016/j.jcss.2021.03.003zbMath1477.68239arXiv2005.01460OpenAlexW3136752844MaRDI QIDQ2037191

Uéverton S. Souza, Paloma T. Lima, Ignasi Sau, Vinícius Fernandes dos Santos

Publication date: 30 June 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

vertex coverfeedback vertex setparameterized complexityedge contractionodd cycle transversalblocker problemgraph transversal

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Reducing the vertex cover number via edge contractions, Using edge contractions to reduce the semitotal domination number

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• The most vital nodes with respect to independent set and vertex cover
• Blockers for the stability number and the chromatic number
• Nonempty intersection of longest paths in series-parallel graphs
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• Graph minors. V. Excluding a planar graph
• The node-deletion problem for hereditary properties is NP-complete
• Hadwiger's conjecture is true for almost every graph
• Which problems have strongly exponential complexity?
• Critical vertices and edges in \(H\)-free graphs
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• On the NP-hardness of edge-deletion and -contraction problems
• Reducing the domination number of graphs via edge contractions and vertex deletions
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Hitting forbidden subgraphs in graphs of bounded treewidth
• Contracting graphs to paths and trees
• A faster FPT algorithm for bipartite contraction
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Hadwiger Number of Graphs with Small Chordality
• Easy problems for tree-decomposable graphs
• Lossy Kernels for Graph Contraction Problems
• Minimum vertex blocker clique problem
• Transversals of Longest Paths and Cycles
• Node-and edge-deletion NP-complete problems
• Obtaining a Bipartite Graph by Contracting Few Edges
• Parameterized Algorithms
• Intersection of longest paths in graph classes
• Transversals of longest paths
• On the complexity of \(k\)-SAT