---
OA_place: publisher
OA_type: hybrid
_id: '20007'
abstract:
- lang: eng
  text: 'There is no known polynomial-time algorithm for graph isomorphism testing,
    but elementary combinatorial “refinement” algorithms seem to be very efficient
    in practice. Some philosophical justification for this phenomenon is provided
    by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time
    combinatorial algorithm (variously known as “naïve refinement”, “naïve vertex
    classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”)
    yields a so-called canonical labelling scheme for “almost all graphs”. More precisely,
    for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm
    assigns labels to vertices in a way that easily permits isomorphism-testing against
    any other graph.'
acknowledgement: All authors were supported by ERC Starting Grant “RANDSTRUCT” No.
  101076777. Michael Anastos was also supported in part by the Austrian Science Fund
  (FWF)[10.55776/ESP3863424] and by the European Union’s Horizon 2020 research and
  innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413.
  For Open Access purposes, the authors have applied a CC BY public copyright license
  to any author accepted manuscript version arising from this submission.
article_processing_charge: Yes (via OA deal)
arxiv: 1
author:
- first_name: Michael
  full_name: Anastos, Michael
  id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
  last_name: Anastos
- first_name: Matthew Alan
  full_name: Kwan, Matthew Alan
  id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
  last_name: Kwan
  orcid: 0000-0002-4003-7567
- first_name: Benjamin
  full_name: Moore, Benjamin
  id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
  last_name: Moore
citation:
  ama: 'Anastos M, Kwan MA, Moore B. Smoothed analysis for graph isomorphism. In:
    <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>. Association
    for Computing Machinery; 2025:2098-2106. doi:<a href="https://doi.org/10.1145/3717823.3718173">10.1145/3717823.3718173</a>'
  apa: 'Anastos, M., Kwan, M. A., &#38; Moore, B. (2025). Smoothed analysis for graph
    isomorphism. In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>
    (pp. 2098–2106). Prague, Czechia: Association for Computing Machinery. <a href="https://doi.org/10.1145/3717823.3718173">https://doi.org/10.1145/3717823.3718173</a>'
  chicago: Anastos, Michael, Matthew Alan Kwan, and Benjamin Moore. “Smoothed Analysis
    for Graph Isomorphism.” In <i>Proceedings of the 57th Annual ACM Symposium on
    Theory of Computing</i>, 2098–2106. Association for Computing Machinery, 2025.
    <a href="https://doi.org/10.1145/3717823.3718173">https://doi.org/10.1145/3717823.3718173</a>.
  ieee: M. Anastos, M. A. Kwan, and B. Moore, “Smoothed analysis for graph isomorphism,”
    in <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>,
    Prague, Czechia, 2025, pp. 2098–2106.
  ista: 'Anastos M, Kwan MA, Moore B. 2025. Smoothed analysis for graph isomorphism.
    Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium
    on Theory of Computing, 2098–2106.'
  mla: Anastos, Michael, et al. “Smoothed Analysis for Graph Isomorphism.” <i>Proceedings
    of the 57th Annual ACM Symposium on Theory of Computing</i>, Association for Computing
    Machinery, 2025, pp. 2098–106, doi:<a href="https://doi.org/10.1145/3717823.3718173">10.1145/3717823.3718173</a>.
  short: M. Anastos, M.A. Kwan, B. Moore, in:, Proceedings of the 57th Annual ACM
    Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp.
    2098–2106.
conference:
  end_date: 2025-06-27
  location: Prague, Czechia
  name: 'STOC: Symposium on Theory of Computing'
  start_date: 2025-06-23
corr_author: '1'
date_created: 2025-07-13T22:01:23Z
date_published: 2025-06-15T00:00:00Z
date_updated: 2025-07-14T06:33:50Z
day: '15'
ddc:
- '000'
department:
- _id: MaKw
doi: 10.1145/3717823.3718173
ec_funded: 1
external_id:
  arxiv:
  - '2410.06095'
file:
- access_level: open_access
  checksum: cf0ab9cb9c6abda188de13dc3f9a4c9b
  content_type: application/pdf
  creator: dernst
  date_created: 2025-07-14T06:13:10Z
  date_updated: 2025-07-14T06:13:10Z
  file_id: '20012'
  file_name: 2025_STOC_Anastos.pdf
  file_size: 706445
  relation: main_file
  success: 1
file_date_updated: 2025-07-14T06:13:10Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 2098-2106
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
  grant_number: '101076777'
  name: Randomness and structure in combinatorics
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
- _id: 8f906bd2-16d5-11f0-9cad-e07be8aa9ac9
  grant_number: ESP3863424
  name: Combinatorial Optimisation Problems on Sparse Random Graphs
publication: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
publication_identifier:
  isbn:
  - '9798400715105'
  issn:
  - 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Smoothed analysis for graph isomorphism
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '20008'
abstract:
- lang: eng
  text: 'We study the complexity of a class of promise graph homomorphism problems.
    For a fixed graph H, the H-colouring problem is to decide whether a given graph
    has a homomorphism to H. By a result of Hell and Nešetřil, this problem is NP-hard
    for any non-bipartite loop-less graph H. Brakensiek and Guruswami [SODA 2018]
    conjectured the hardness extends to promise graph homomorphism problems as follows:
    fix a pair of non-bipartite loop-less graphs G, H such that there is a homomorphism
    from G to H, it is NP-hard to distinguish between graphs that are G-colourable
    and those that are not H-colourable. We confirm this conjecture in the cases when
    both G and H are 4-colourable. This is a common generalisation of previous results
    of Khanna, Linial, and Safra [Comb. 20(3): 393-415 (2000)] and of Krokhin and
    Opršal [FOCS 2019]. The result is obtained by combining the algebraic approach
    to promise constraint satisfaction with methods of topological combinatorics and
    equivariant obstruction theory.'
acknowledgement: This research was supported by the Austrian Science Fund (FWF project
  P31312-N35) and by project MSCAfellow5_MUNI (CZ.02.01.01/00/22_010/0003229) financed
  by the Ministry of Education, Youth and Sports of the Czech Republic. This project
  has also received funding from the European Union’s Horizon 2020 research and innovation
  programme under the Marie Skłodowska-Curie Grant Agreement No 101034413.
article_processing_charge: Yes (in subscription journal)
author:
- first_name: Sergey
  full_name: Avvakumov, Sergey
  id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
  last_name: Avvakumov
  orcid: 0000-0002-7840-5062
- first_name: Marek
  full_name: Filakovský, Marek
  id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
  last_name: Filakovský
- first_name: Jakub
  full_name: Opršal, Jakub
  id: ec596741-c539-11ec-b829-c79322a91242
  last_name: Opršal
  orcid: 0000-0003-1245-3456
- first_name: Gianluca
  full_name: Tasinato, Gianluca
  id: 0433290C-AF8F-11E9-A4C7-F729E6697425
  last_name: Tasinato
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: 'Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. Hardness of 4-colouring
    G-colourable graphs. In: <i>Proceedings of the 57th Annual ACM Symposium on Theory
    of Computing</i>. Association for Computing Machinery; 2025:72-83. doi:<a href="https://doi.org/10.1145/3717823.3718154">10.1145/3717823.3718154</a>'
  apa: 'Avvakumov, S., Filakovský, M., Opršal, J., Tasinato, G., &#38; Wagner, U.
    (2025). Hardness of 4-colouring G-colourable graphs. In <i>Proceedings of the
    57th Annual ACM Symposium on Theory of Computing</i> (pp. 72–83). Prague, Czechia:
    Association for Computing Machinery. <a href="https://doi.org/10.1145/3717823.3718154">https://doi.org/10.1145/3717823.3718154</a>'
  chicago: Avvakumov, Sergey, Marek Filakovský, Jakub Opršal, Gianluca Tasinato, and
    Uli Wagner. “Hardness of 4-Colouring G-Colourable Graphs.” In <i>Proceedings of
    the 57th Annual ACM Symposium on Theory of Computing</i>, 72–83. Association for
    Computing Machinery, 2025. <a href="https://doi.org/10.1145/3717823.3718154">https://doi.org/10.1145/3717823.3718154</a>.
  ieee: S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, and U. Wagner, “Hardness
    of 4-colouring G-colourable graphs,” in <i>Proceedings of the 57th Annual ACM
    Symposium on Theory of Computing</i>, Prague, Czechia, 2025, pp. 72–83.
  ista: 'Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. 2025. Hardness
    of 4-colouring G-colourable graphs. Proceedings of the 57th Annual ACM Symposium
    on Theory of Computing. STOC: Symposium on Theory of Computing, 72–83.'
  mla: Avvakumov, Sergey, et al. “Hardness of 4-Colouring G-Colourable Graphs.” <i>Proceedings
    of the 57th Annual ACM Symposium on Theory of Computing</i>, Association for Computing
    Machinery, 2025, pp. 72–83, doi:<a href="https://doi.org/10.1145/3717823.3718154">10.1145/3717823.3718154</a>.
  short: S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, U. Wagner, in:, Proceedings
    of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing
    Machinery, 2025, pp. 72–83.
conference:
  end_date: 2025-06-27
  location: Prague, Czechia
  name: 'STOC: Symposium on Theory of Computing'
  start_date: 2025-06-23
corr_author: '1'
date_created: 2025-07-13T22:01:23Z
date_published: 2025-06-15T00:00:00Z
date_updated: 2026-04-07T12:36:50Z
day: '15'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.1145/3717823.3718154
ec_funded: 1
file:
- access_level: open_access
  checksum: 2c9ae7ad0102c41124976f4cb5182760
  content_type: application/pdf
  creator: dernst
  date_created: 2025-07-14T06:42:58Z
  date_updated: 2025-07-14T06:42:58Z
  file_id: '20013'
  file_name: 2025_STOC_Avvakumov.pdf
  file_size: 940827
  relation: main_file
  success: 1
file_date_updated: 2025-07-14T06:42:58Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 72-83
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P31312
  name: Algorithms for Embeddings and Homotopy Theory
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
publication_identifier:
  isbn:
  - '9798400715105'
  issn:
  - 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
  record:
  - id: '20339'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Hardness of 4-colouring G-colourable graphs
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...