4 papers
Cut-homotopies and the complexity of edge-coloring problems
Alexey Barsukov, Roman Feller, Maximilian Hadek +1
We study the computational complexity of problems that ask if a given graph admits an edge-coloring that does not contain an edge-colored clique from some fixed finite family. We s…
A categorical perspective on constraint satisfaction: The wonderland of adjunctions
Maximilian Hadek, Tomáš Jakl, Jakub Opršal
The so-called algebraic approach to the constraint satisfaction problem (CSP) has been a prevalent method of the study of complexity of these problems since early 2000's. The core…
Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
Libor Barto, Maximilian Hadek, Dmitriy Zhuk
We develop a unified framework to characterize the power of higher-level algorithms for the constraint satisfaction problem (CSP), such as -consistency, the Sherali-Adams LP hie…
KÅnig = Ramsey, A compactness lemma for Ramsey categories
Maximilian Hadek
We prove a new characterization of the Ramsey property of categories in terms of a generalized form of KÅnig's tree lemma. Afterwards, we discuss its applications to structural Ra…