Reducing graph transversals via edge contractions

DOI10.4230/LIPICS.MFCS.2020.64MaRDI QIDQ5089236FDOQ5089236

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

Publication date: 18 July 2022

Recommendations

• Reducing graph transversals via edge contractions
• Reducing the domination number of graphs via edge contractions
• Reducing the domination number of graphs via edge contractions and vertex deletions
• Item:QQ2441588
• Item:QQ2441588

zbMATH Keywords

parameterized complexityvertex coveredge contractionfeedback vertex setodd cycle transversalblocker problemgraph transversal

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• 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?
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• Parameterized algorithms
• On the complexity of \(k\)-SAT
• Graph minors. V. Excluding a planar graph
• Node-and edge-deletion NP-complete problems
• Transversals of Longest Paths and Cycles
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• The most vital nodes with respect to independent set and vertex cover
• Minimum vertex blocker clique problem
• Blockers for the stability number and the chromatic number
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Obtaining a bipartite graph by contracting few edges
• On the NP-hardness of edge-deletion and -contraction problems
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• Nonempty intersection of longest paths in series-parallel graphs
• Lossy kernels for graph contraction problems
• Title not available (Why is that?)
• Critical vertices and edges in \(H\)-free graphs
• Intersection of longest paths in graph classes
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Hitting forbidden subgraphs in graphs of bounded treewidth
• Title not available (Why is that?)

Cited In (2)

• Title not available (Why is that?)
• The complexity of blocking (semi)total dominating sets with edge contractions

This page was built for publication: Reducing graph transversals via edge contractions

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