Autor(es)

Couto, Yan S. ; Fernandes, Cristina G.

• Tipo de documento: Artigo Científico
• Fonte: APPROXIMATION AND ONLINE ALGORITHMS, WAOA 2025; v. 16077, p. 17-pg., 2026-01-01.

Resumo

The k-core of a graph is its maximal subgraph with minimum degree at least.k, and the core value of a vertex.u is the largest.k for which.u is contained in the k-core of the graph. Among cohesive subgraphs, k-core and its variants have received a lot of attention recently, particularly on dynamic graphs, as reported by Hanauer, Henzinger, and Schulz in their recent survey on dynamic graph algorithms. We answer questions on.k-core stated in the survey, proving that there is no efficient dynamic algorithm for k-core or to find.(2 - E)-approximations for the core values, unless we can improve decade-long state-of-the-art algorithms in many areas including matrix multiplication and satisfiability, based on the established OMv conjecture and SETH. Our results show that there is no dynamic algorithm for.k-core asymptotically faster than the trivial ones, and we derive them via proving hardness results for a dynamic version of the circuit value problem. This explains why most recent research papers in this area focus not on a generic efficient dynamic algorithm, but on finding a bounded algorithm, which is fast when few core values change per update. However, we also prove that such bounded algorithms do not exist, based on the OMv conjecture. We also obtain lower bounds for a directed version of the problem, and for the edge variant of the problem, known as.k-truss. On the positive side, we present a polylogarithmic dynamic algorithm for 2-core. (AU)

• Processo FAPESP: 24/18049-0 - Subgrafos coesos
• Beneficiário: Yan Soares Couto
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 23/03167-5 - Combinatória clássica, assintótica, quântica e geométrica
• Beneficiário: Yoshiharu Kohayakawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático