Reducing the vertex cover number via edge contractions

DOI10.1016/j.jcss.2023.03.003arXiv2202.03322MaRDI QIDQ6098145

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

Publication date: 12 June 2023

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

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

zbMATH Keywords

vertex coverparameterized complexityedge contractionblocker problems

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Increasing the minimum degree of a graph by contractions
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• The most vital nodes with respect to independent set and vertex cover
• Parameterized complexity of three edge contraction problems with degree constraints
• Blockers for the stability number and the chromatic number
• Improved upper bounds for vertex cover
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• The node-deletion problem for hereditary properties is NP-complete
• Critical vertices and edges in \(H\)-free graphs
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• An FPT algorithm for contraction to cactus
• On the NP-hardness of edge-deletion and -contraction problems
• Parameterized complexity of finding subgraphs with hereditary properties.
• Obtaining planarity by contracting few edges
• Paths to trees and cacti
• On the parameterized complexity of contraction to generalization of trees
• Blocking total dominating sets via edge contractions
• Reducing graph transversals via edge contractions
• Complexity and algorithms for constant diameter augmentation problems
• Using edge contractions to reduce the semitotal domination number
• Reducing the domination number of graphs via edge contractions and vertex deletions
• Reducing the domination number of \(( P_3 + k P_2 )\)-free graphs via one edge contraction
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• 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
• Contracting Few Edges to Remove Forbidden Induced Subgraphs
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
• Minimum vertex blocker clique problem
• Kernelization
• On the Parameterized Complexity of Contraction to Generalization of Trees.
• Split Contraction
• Node-and edge-deletion NP-complete problems
• Obtaining a Bipartite Graph by Contracting Few Edges
• Parameterized Algorithms
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• On the Parameterized Complexity Of Grid Contraction

This page was built for publication: Reducing the vertex cover number via edge contractions