Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2404.09236 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913799534018560 |
|---|---|
| author | Lima, Carlos V. G. C. Marcilon, Thiago de Medeiros, Pedro Paulo |
| author_facet | Lima, Carlos V. G. C. Marcilon, Thiago de Medeiros, Pedro Paulo |
| contents | The subject of graph convexity is well explored in the literature, the so-called interval convexities above all. In this work, we explore the cycle convexity, an interval convexity whose interval function is $I(S) = S \cup \{u \mid G[S \cup \{u\}]$ has a cycle containing $u\}$. In this convexity, we prove that determine whether the convexity number of a graph $G$ is at least $k$ is \NP-complete and \W[1]-hard when parameterized by the size of the solution when $G$ is a thick spider, but polynomial when $G$ is an extended $P_4$-laden graph. We also prove that determining whether the percolation time of a graph is at least $k$ is \NP-complete even for fixed $k \geq 9$, but polynomial for cacti or for fixed $k\leq2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_09236 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The complexity of convexity number and percolation time in the cycle convexity Lima, Carlos V. G. C. Marcilon, Thiago de Medeiros, Pedro Paulo Computational Complexity The subject of graph convexity is well explored in the literature, the so-called interval convexities above all. In this work, we explore the cycle convexity, an interval convexity whose interval function is $I(S) = S \cup \{u \mid G[S \cup \{u\}]$ has a cycle containing $u\}$. In this convexity, we prove that determine whether the convexity number of a graph $G$ is at least $k$ is \NP-complete and \W[1]-hard when parameterized by the size of the solution when $G$ is a thick spider, but polynomial when $G$ is an extended $P_4$-laden graph. We also prove that determining whether the percolation time of a graph is at least $k$ is \NP-complete even for fixed $k \geq 9$, but polynomial for cacti or for fixed $k\leq2$. |
| title | The complexity of convexity number and percolation time in the cycle convexity |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2404.09236 |