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!
|
| _version_ | 1866915503322169344 |
|---|---|
| author | Ali, Shanookha |
| author_facet | Ali, Shanookha |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_16185 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hardness and Structural Properties of Fuzzy Edge Contraction Ali, Shanookha Combinatorics Logic 05C22, 05C90, 68R10 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. |
| title | Hardness and Structural Properties of Fuzzy Edge Contraction |
| topic | Combinatorics Logic 05C22, 05C90, 68R10 |
| url | https://arxiv.org/abs/2509.16185 |