---
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: Proceedings of the 57th Annual ACM Symposium on Theory
of Computing. Association for Computing Machinery; 2025:72-83. doi:10.1145/3717823.3718154'
apa: 'Avvakumov, S., Filakovský, M., Opršal, J., Tasinato, G., & Wagner, U.
(2025). Hardness of 4-colouring G-colourable graphs. In Proceedings of the
57th Annual ACM Symposium on Theory of Computing (pp. 72–83). Prague, Czechia:
Association for Computing Machinery. https://doi.org/10.1145/3717823.3718154'
chicago: Avvakumov, Sergey, Marek Filakovský, Jakub Opršal, Gianluca Tasinato, and
Uli Wagner. “Hardness of 4-Colouring G-Colourable Graphs.” In Proceedings of
the 57th Annual ACM Symposium on Theory of Computing, 72–83. Association for
Computing Machinery, 2025. https://doi.org/10.1145/3717823.3718154.
ieee: S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, and U. Wagner, “Hardness
of 4-colouring G-colourable graphs,” in Proceedings of the 57th Annual ACM
Symposium on Theory of Computing, 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.” Proceedings
of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing
Machinery, 2025, pp. 72–83, doi:10.1145/3717823.3718154.
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'
...
---
_id: '15168'
abstract:
- lang: eng
text: 'A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its
vertices with colours 1, … , k such that each edge contains a unique maximal colour.
Deciding whether an input hypergraph admits LO k-colouring with a fixed number
of colours is NP-complete (and in the special case of graphs, LO colouring coincides
with the usual graph colouring). Here, we investigate the complexity of approximating
the "linearly ordered chromatic number" of a hypergraph. We prove that the following
promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between
the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable.
We prove this result by a combination of algebraic, topological, and combinatorial
methods, building on and extending a topological approach for studying approximate
graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).'
acknowledgement: "Marek Filakovský: This research was supported by Charles University
(project PRIMUS/\r\n21/SCI/014), the Austrian Science Fund (FWF project P31312-N35),
and MSCAfellow5_MUNI\r\n(CZ.02.01.01/00/22_010/0003229). Tamio-Vesa Nakajima: This
research was funded by UKRI EP/X024431/1 and by a Clarendon Fund Scholarship. All
data is provided in full in the results section of this paper. Jakub Opršal: This
project has received funding from the European Union’s Horizon 2020 research and
innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413.
Uli Wagner: This research was supported by the Austrian Science Fund (FWF project
P31312-N35)."
alternative_title:
- LIPIcs
article_number: '34'
article_processing_charge: No
arxiv: 1
author:
- first_name: Marek
full_name: Filakovský, Marek
id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
last_name: Filakovský
- first_name: Tamio Vesa
full_name: Nakajima, Tamio Vesa
last_name: Nakajima
- 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: 'Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly
ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In: 41st International
Symposium on Theoretical Aspects of Computer Science. Vol 289. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.STACS.2024.34'
apa: 'Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., & Wagner, U.
(2024). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs.
In 41st International Symposium on Theoretical Aspects of Computer Science
(Vol. 289). Clermont-Ferrand, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.STACS.2024.34'
chicago: Filakovský, Marek, Tamio Vesa Nakajima, Jakub Opršal, Gianluca Tasinato,
and Uli Wagner. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform
Hypergraphs.” In 41st International Symposium on Theoretical Aspects of Computer
Science, Vol. 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
https://doi.org/10.4230/LIPIcs.STACS.2024.34.
ieee: M. Filakovský, T. V. Nakajima, J. Opršal, G. Tasinato, and U. Wagner, “Hardness
of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs,” in 41st
International Symposium on Theoretical Aspects of Computer Science, Clermont-Ferrand,
France, 2024, vol. 289.
ista: 'Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. 2024. Hardness
of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. 41st International
Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical
Aspects of Computer Science, LIPIcs, vol. 289, 34.'
mla: Filakovský, Marek, et al. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable
3-Uniform Hypergraphs.” 41st International Symposium on Theoretical Aspects
of Computer Science, vol. 289, 34, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2024, doi:10.4230/LIPIcs.STACS.2024.34.
short: M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, in:, 41st
International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-03-14
location: Clermont-Ferrand, France
name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
start_date: 2024-03-12
corr_author: '1'
date_created: 2024-03-24T23:00:59Z
date_published: 2024-03-01T00:00:00Z
date_updated: 2026-04-07T12:36:50Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.STACS.2024.34
ec_funded: 1
external_id:
arxiv:
- '2312.12981'
isi:
- '001300393400034'
file:
- access_level: open_access
checksum: 0524d4189fd1ed08989546511343edf3
content_type: application/pdf
creator: dernst
date_created: 2024-03-25T07:44:30Z
date_updated: 2024-03-25T07:44:30Z
file_id: '15175'
file_name: 2024_LIPICs_Filakovsky.pdf
file_size: 927290
relation: main_file
success: 1
file_date_updated: 2024-03-25T07:44:30Z
has_accepted_license: '1'
intvolume: ' 289'
isi: 1
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
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: 41st International Symposium on Theoretical Aspects of Computer Science
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959773119'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '20339'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 289
year: '2024'
...
---
_id: '12563'
abstract:
- lang: eng
text: 'he approximate graph coloring problem, whose complexity is unresolved in
most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable,
where c≥k. This problem naturally generalizes to promise graph homomorphism problems
and further to promise constraint satisfaction problems. The complexity of these
problems has recently been studied through an algebraic approach. In this paper,
we introduce two new techniques to analyze the complexity of promise CSPs: one
is based on topology and the other on adjunction. We apply these techniques, together
with the previously introduced algebraic approach, to obtain new unconditional
NP-hardness results for a significant class of approximate graph coloring and
promise graph homomorphism problems.'
acknowledgement: "Andrei Krokhin and Jakub Opršal were supported by the UK EPSRC grant
EP/R034516/1. Jakub Opršal has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement
No 101034413. Stanislav Živný was supported by a Royal Society University Research
Fellowship. This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No 714532). The paper re\x1Eects only the authors’ views and not
the views of the ERC or the European Commission. "
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Andrei
full_name: Krokhin, Andrei
last_name: Krokhin
- 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: Marcin
full_name: Wrochna, Marcin
last_name: Wrochna
- first_name: Stanislav
full_name: Živný, Stanislav
last_name: Živný
citation:
ama: Krokhin A, Opršal J, Wrochna M, Živný S. Topology and adjunction in promise
constraint satisfaction. SIAM Journal on Computing. 2023;52(1):38-79. doi:10.1137/20m1378223
apa: Krokhin, A., Opršal, J., Wrochna, M., & Živný, S. (2023). Topology and
adjunction in promise constraint satisfaction. SIAM Journal on Computing.
Society for Industrial and Applied Mathematics. https://doi.org/10.1137/20m1378223
chicago: Krokhin, Andrei, Jakub Opršal, Marcin Wrochna, and Stanislav Živný. “Topology
and Adjunction in Promise Constraint Satisfaction.” SIAM Journal on Computing.
Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/20m1378223.
ieee: A. Krokhin, J. Opršal, M. Wrochna, and S. Živný, “Topology and adjunction
in promise constraint satisfaction,” SIAM Journal on Computing, vol. 52,
no. 1. Society for Industrial and Applied Mathematics, pp. 38–79, 2023.
ista: Krokhin A, Opršal J, Wrochna M, Živný S. 2023. Topology and adjunction in
promise constraint satisfaction. SIAM Journal on Computing. 52(1), 38–79.
mla: Krokhin, Andrei, et al. “Topology and Adjunction in Promise Constraint Satisfaction.”
SIAM Journal on Computing, vol. 52, no. 1, Society for Industrial and Applied
Mathematics, 2023, pp. 38–79, doi:10.1137/20m1378223.
short: A. Krokhin, J. Opršal, M. Wrochna, S. Živný, SIAM Journal on Computing 52
(2023) 38–79.
date_created: 2023-02-16T07:03:52Z
date_published: 2023-01-01T00:00:00Z
date_updated: 2025-05-14T10:51:32Z
day: '01'
department:
- _id: UlWa
doi: 10.1137/20m1378223
ec_funded: 1
external_id:
arxiv:
- '2003.11351'
isi:
- '000955000000001'
intvolume: ' 52'
isi: 1
issue: '1'
keyword:
- General Mathematics
- General Computer Science
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2003.11351
month: '01'
oa: 1
oa_version: Preprint
page: 38-79
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Topology and adjunction in promise constraint satisfaction
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 52
year: '2023'
...
---
_id: '11991'
abstract:
- lang: eng
text: The study of the complexity of the constraint satisfaction problem (CSP),
centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in
the last two decades. After a long concerted effort and many partial results,
the Dichotomy Conjecture has been proved in 2017 independently by Bulatov and
Zhuk. At about the same time, a vast generalisation of CSP, called promise CSP,
has started to gain prominence. In this survey, we explain the importance of promise
CSP and highlight many new very interesting features that the study of promise
CSP has brought to light. The complexity classification quest for the promise
CSP is wide open, and we argue that, despite the promise CSP being more general,
this quest is rather more accessible to a wide range of researchers than the dichotomy-led
study of the CSP has been.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Andrei
full_name: Krokhin, Andrei
last_name: Krokhin
- first_name: Jakub
full_name: Opršal, Jakub
id: ec596741-c539-11ec-b829-c79322a91242
last_name: Opršal
orcid: 0000-0003-1245-3456
citation:
ama: Krokhin A, Opršal J. An invitation to the promise constraint satisfaction problem.
ACM SIGLOG News. 2022;9(3):30-59. doi:10.1145/3559736.3559740
apa: Krokhin, A., & Opršal, J. (2022). An invitation to the promise constraint
satisfaction problem. ACM SIGLOG News. Association for Computing Machinery.
https://doi.org/10.1145/3559736.3559740
chicago: Krokhin, Andrei, and Jakub Opršal. “An Invitation to the Promise Constraint
Satisfaction Problem.” ACM SIGLOG News. Association for Computing Machinery,
2022. https://doi.org/10.1145/3559736.3559740.
ieee: A. Krokhin and J. Opršal, “An invitation to the promise constraint satisfaction
problem,” ACM SIGLOG News, vol. 9, no. 3. Association for Computing Machinery,
pp. 30–59, 2022.
ista: Krokhin A, Opršal J. 2022. An invitation to the promise constraint satisfaction
problem. ACM SIGLOG News. 9(3), 30–59.
mla: Krokhin, Andrei, and Jakub Opršal. “An Invitation to the Promise Constraint
Satisfaction Problem.” ACM SIGLOG News, vol. 9, no. 3, Association for
Computing Machinery, 2022, pp. 30–59, doi:10.1145/3559736.3559740.
short: A. Krokhin, J. Opršal, ACM SIGLOG News 9 (2022) 30–59.
date_created: 2022-08-27T11:23:37Z
date_published: 2022-07-01T00:00:00Z
date_updated: 2022-09-05T08:19:38Z
day: '01'
department:
- _id: UlWa
doi: 10.1145/3559736.3559740
external_id:
arxiv:
- '2208.13538'
intvolume: ' 9'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/2208.13538
month: '07'
oa: 1
oa_version: Preprint
page: 30-59
publication: ACM SIGLOG News
publication_identifier:
issn:
- 2372-3491
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: An invitation to the promise constraint satisfaction problem
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9
year: '2022'
...