22 citations · 107 across the 16 of their papers we have counts for
27 papers
A note on hardness of promise hypergraph colouring
Marcin Wrochna
We show a slightly simpler proof the following theorem by I. Dinur, O. Regev, and C. Smyth: for all , it is NP-hard to find a -colouring of a 2-coloruable 3-uniform hy…
Smaller counterexamples to Hedetniemi's conjecture
Marcin Wrochna
Hedetniemi's conjecture~\cite{hedetniemi1966homomorphisms} for -colorings states that the tensor product is -colorable if and only if or is -colorable…
PTAS for Sparse General-Valued CSPs
Balázs F. Mezei, Marcin Wrochna, Stanislav Živný
We study polynomial-time approximation schemes (PTASes) for constraint satisfaction problems (CSPs) such as Maximum Independent Set or Minimum Vertex Cover on sparse graph classes.…
Integer Programming and Incidence Treedepth
Eduard Eiben, Robert Ganian, Dušan Knop +3
Recently a strong connection has been shown between the tractability of integer programming (IP) with bounded coefficients on the one side and the structure of its constraint matri…
Sallow: a heuristic algorithm for treedepth decompositions
Marcin Wrochna
We describe a heuristic algorithm for computing treedepth decompositions, submitted for the PACE 2020 challenge. It relies on a variety of greedy algorithms computing elimination o…
Topology and adjunction in promise constraint satisfaction
Andrei Krokhin, Jakub Opršal, Marcin Wrochna +1
The approximate graph colouring problem, whose complexity is unresolved in most cases, concerns finding a -colouring of a graph that is promised to be -colourable, where $c\g…