Contracting edges to destroy a pattern: A complexity study
February 27, 2023 Β· Declared Dead Β· π International Symposium on Fundamentals of Computation Theory
"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 Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
π Similar Papers
In the same crypt β Data Structures & Algorithms
π
π
The Cartographer
R.I.P.
π»
Ghosted
Route Planning in Transportation Networks
R.I.P.
π»
Ghosted
Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
R.I.P.
π»
Ghosted
Hierarchical Clustering: Objective Functions and Algorithms
R.I.P.
π»
Ghosted
Graph Isomorphism in Quasipolynomial Time
π
π
The Cartographer
Simulation optimization: A review of algorithms and applications
Died the same way β π» Ghosted
R.I.P.
π»
Ghosted
Federated Learning: Strategies for Improving Communication Efficiency
R.I.P.
π»
Ghosted
In-Datacenter Performance Analysis of a Tensor Processing Unit
R.I.P.
π»
Ghosted
Deep Convolutional Neural Networks for Computer-Aided Detection: CNN Architectures, Dataset Characteristics and Transfer Learning
R.I.P.
π»
Ghosted