Reducing graph transversals via edge contractions

DOI10.1016/J.JCSS.2021.03.003MaRDI QIDQ2037191zbMATH OpenOpenAlexFDO

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

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, https://drops.dagstuhl.de/opus/volltexte/2020/12734/

zbMATH Keywords

blocker problemedge contractionfeedback vertex setgraph transversalodd cycle transversalparameterized complexityvertex cover

Mathematics Subject Classification ID

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

Abstract: For a graph invariant $pi$, the Contraction($pi$) problem consists in, given a graph $G$ and two positive integers $k,d$, deciding whether one can contract at most $k$ edges of $G$ to obtain a graph in which $pi$ has dropped by at least $d$. Galby et al. [ISAAC 2019, MFCS 2019] recently studied the case where $pi$ is the size of a minimum dominating set. We focus on graph invariants defined as the minimum size of a vertex set that hits all the occurrences of graphs in a collection $calH$ according to a fixed containment relation. We prove co-NP-hardness results under some assumptions on the graphs in $calH$, which in particular imply that Contraction($pi$) is co-NP-hard even for fixed $k=d=1$ when $pi$ is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, we show that when $pi$ is the size of a minimum vertex cover, the problem is in XP parameterized by $d$.

Recommendations

• Reducing the domination number of graphs via edge contractions and vertex deletions
• On contracting graphs to fixed pattern graphs
• Contracting few edges to remove forbidden induced subgraphs

Cites work

• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• Blockers for the stability number and the chromatic number
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Critical vertices and edges in \(H\)-free graphs
• Easy problems for tree-decomposable graphs
• Fundamentals of parameterized complexity
• Graph minors. V. Excluding a planar graph
• Graph theory
• Hadwiger's conjecture is true for almost every graph
• Hitting forbidden subgraphs in graphs of bounded treewidth
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Intersection of longest paths in graph classes
• Lossy kernels for graph contraction problems
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• Minimum vertex blocker clique problem
• Node-and edge-deletion NP-complete problems
• Nonempty intersection of longest paths in series-parallel graphs
• Obtaining a bipartite graph by contracting few edges
• On the complexity of k-SAT
• On the NP-hardness of edge-deletion and -contraction problems
• Parameterized algorithms
• Reducing the domination number of graphs via edge contractions and vertex deletions
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The most vital nodes with respect to independent set and vertex cover
• The node-deletion problem for hereditary properties is NP-complete
• Transversals of Longest Paths and Cycles
• Which problems have strongly exponential complexity?

Cited in

(7)

• Blocking total dominating sets via edge contractions
• Using edge contractions to reduce the semitotal domination number
• Reducing the domination number of graphs via edge contractions and vertex deletions
• scientific article; zbMATH DE number 1222899 (Why is no real title available?)
• Reducing graph transversals via edge contractions
• Reducing the vertex cover number via edge contractions
• Distance-preserving graph compression techniques

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 Q2037191)