Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.16185 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- We investigate the computational complexity of edge-deletion and edge-contraction problems in fuzzy graphs. For any graph property Π that is hereditary under contractions (or deletions) and determined by 3-connected components, the corresponding fuzzy edge-deletion (FPED) and fuzzy edge-contraction (FPEC) problems are NP- hard. Our results hold under both fixed-threshold (α_0) and all-threshold (\forall α) semantics, and apply even to restricted classes of fuzzy graphs such as fuzzy 3-connected or fuzzy bipartite graphs. We further demonstrate that well-known properties, including planarity and series-parallelness, satisfy these conditions, making the fuzzy versions of these classical graph problems computationally intractable. The proofs leverage reductions from classical NP-hard problems and generalize the constructions to the fuzzy setting while preserving key structural properties.