{"ID":2876175,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.00721","arxiv_id":"2509.00721","title":"Large cliques and large independent sets: can they coexist?","abstract":"For a graph $G$ and a parameter $k$, we call a vertex $k$-enabling if it belongs both to a clique of size $k$ and to an independent set of size $k$, and we call it $k$-excluding otherwise. Motivated by issues that arise in secret sharing schemes, we study the complexity of detecting vertices that are $k$-excluding. We show that for every $ε$, for sufficiently large $n$, if $k \u003e (\\frac{1}{4} + ε)n$, then every graph on $n$ vertices must have a $k$-excluding vertex, and moreover, such a vertex can be found in polynomial time. In contrast, if $k \u003c (\\frac{1}{4} - ε)n$, a regime in which it might be that all vertices are $k$-enabling, deciding whether a graph has no $k$-excluding vertex is NP-hard.","short_abstract":"For a graph $G$ and a parameter $k$, we call a vertex $k$-enabling if it belongs both to a clique of size $k$ and to an independent set of size $k$, and we call it $k$-excluding otherwise. Motivated by issues that arise in secret sharing schemes, we study the complexity of detecting vertices that are $k$-excluding. We...","url_abs":"https://arxiv.org/abs/2509.00721","url_pdf":"https://arxiv.org/pdf/2509.00721v1","authors":"[\"Uriel Feige\",\"Ilia Pauzner\"]","published":"2025-08-31T07:00:43Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}