Contracting edges to destroy a pattern: A complexity study

February 27, 2023 Β· Declared Dead Β· πŸ› International Symposium on Fundamentals of Computation Theory

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Dipayan Chakraborty, R. B. Sandeep arXiv ID 2302.13605 Category cs.DS: Data Structures & Algorithms Cross-listed math.CO Citations 1 Venue International Symposium on Fundamentals of Computation Theory Last Checked 4 months ago
Abstract
Given a graph G and an integer k, the objective of the $Ξ $-Contraction problem is to check whether there exists at most k edges in G such that contracting them in G results in a graph satisfying the property $Ξ $. We investigate the problem where $Ξ $ is `H-free' (without any induced copies of H). It is trivial that H-free Contraction is polynomial-time solvable if H is a complete graph of at most two vertices. We prove that, in all other cases, the problem is NP-complete. We then investigate the fixed-parameter tractability of these problems. We prove that whenever H is a tree, except for seven trees, H-free Contraction is W[2]-hard. This result along with the known results leaves behind three unknown cases among trees.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted