Constructing self-referential instances for the clique problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912878539309056 |
|---|---|
| author | Li, Jiaqi Hu, Shuli Li, Xianxian Yin, Minghao |
| author_facet | Li, Jiaqi Hu, Shuli Li, Xianxian Yin, Minghao |
| contents | In this paper, we propose constructing self-referential instances to reveal the inherent algorithmic hardness of the clique problem. First, we prove the existence of a phase transition phenomenon for the clique problem in the Erdős--Rényi random graph model and derive an exact location for the transition point. Subsequently, at the transition point, we construct a family of graphs. In this family, each graph shares the same number of vertices, number of edges, and degree sequence, yet both instances containing a $k$-clique and instances without any $k$-clique are included. These two states can be transformed into each other through a symmetric transformation that preserves the degree of every vertex. This property explains why exhaustive search is required in the critical region: an algorithm must search nearly the entire solution space to determine the existence of a solution; otherwise, a counterinstance can be constructed from the original instance using the symmetric transformation. Finally, this paper elaborates on the intrinsic reason for this phenomenon from the independence of the solution space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_19393 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Constructing self-referential instances for the clique problem Li, Jiaqi Hu, Shuli Li, Xianxian Yin, Minghao Computational Complexity Data Structures and Algorithms In this paper, we propose constructing self-referential instances to reveal the inherent algorithmic hardness of the clique problem. First, we prove the existence of a phase transition phenomenon for the clique problem in the Erdős--Rényi random graph model and derive an exact location for the transition point. Subsequently, at the transition point, we construct a family of graphs. In this family, each graph shares the same number of vertices, number of edges, and degree sequence, yet both instances containing a $k$-clique and instances without any $k$-clique are included. These two states can be transformed into each other through a symmetric transformation that preserves the degree of every vertex. This property explains why exhaustive search is required in the critical region: an algorithm must search nearly the entire solution space to determine the existence of a solution; otherwise, a counterinstance can be constructed from the original instance using the symmetric transformation. Finally, this paper elaborates on the intrinsic reason for this phenomenon from the independence of the solution space. |
| title | Constructing self-referential instances for the clique problem |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.19393 |