10 citations · 12 across the 9 of their papers we have counts for
15 papers
Space-Efficient Hierholzer for Undirected Graphs
Elena Grigorescu, Ziad Ismaili Alaoui, Tamio-Vesa Nakajima +2
We present a simple linear-time algorithm that outputs an Eulerian tour of an undirected multigraph with vertices and edges, if one exists, in time and using …
Towards infinite PCSP: a dichotomy for monochromatic cliques
Demian Banakh, Alexey Barsukov, Tamio-Vesa Nakajima
The logic MMSNP is a well-studied fragment of Existential Second-Order logic that, from a computational perspective, captures finite-domain Constraint Satisfaction Problems (CSPs)…
Virtual-Memory Powersort
Finn Moltmann, Tamio-Vesa Nakajima, Sebastian Wild
We give a more space-efficient implementation of adaptive mergesort: Virtual-Memory Powersort. Using internal buffering techniques, we significantly reduce the memory consumption o…
Rooting Out Entropy: Optimal Tree Extraction for Ultra-Succinct Graphs
Ziad Ismaili Alaoui, Tamio-Vesa Nakajima, Namrata +1
We combine two methods for the lossless compression of unlabeled graphs - entropy compressing adjacency lists and computing canonical names for vertices - and solve an ensuing nove…
Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
Benjamin Bedert, Tamio-Vesa Nakajima, Karolina Okrasa +1
We introduce a new notion of sparsification, called \emph{strong sparsification}, in which constraints are not removed but variables can be merged. As our main result, we present a…
Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna +1
Using the algebraic approach to promise constraint satisfaction problems, we establish complexity classifications of three natural variants of hypergraph colourings: standard nonmo…
Maximum And- vs. Even-SAT
Tamio-Vesa Nakajima, Stanislav Živný
A multiset of literals, called a clause, is \emph{strongly satisfied} by an assignment if \emph{no} literal evaluates to false. Finding an assignment that maximises the number of s…
A Dichotomy for Maximum PCSPs on Graphs
Tamio-Vesa Nakajima, Stanislav Živný
Fix two non-empty loopless graphs and such that maps homomorphically to . The Maximum Promise Constraint Satisfaction Problem parameterised by and is the fol…
A logarithmic approximation of linearly ordered colourings
Johan Håstad, Björn Martinsson, Tamio-Vesa Nakajima +1
A linearly ordered (LO) -colouring of a hypergraph assigns to each vertex a colour from the set in such a way that each hyperedge has a unique maximum eleme…
An approximation algorithm for Maximum DiCut vs. Cut
Tamio-Vesa Nakajima, Stanislav Živný
Goemans and Williamson designed a 0.878-approximation algorithm for Max-Cut in undirected graphs [JACM'95]. Khot, Kindler, Mosel, and O'Donnel showed that the approximation ratio o…
Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal +2
A linearly ordered (LO) -colouring of a hypergraph is a colouring of its vertices with colours such that each edge contains a unique maximal colour. Deciding wheth…
Maximum - vs. -colourings of graphs
Tamio-Vesa Nakajima, Stanislav Živný
We present polynomial-time SDP-based algorithms for the following problem: For fixed , given a real number and a graph that admits a -colouring with a …
1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
Lorenzo Ciardo, Marcin Kozik, Andrei Krokhin +2
The 1-in-3 and Not-All-Equal satisfiability problems for Boolean CNF formulas are two well-known NP-hard problems. In contrast, the promise 1-in-3 vs. Not-All-Equal problem can be…
On the complexity of symmetric vs. functional PCSPs
Tamio-Vesa Nakajima, Stanislav Živný
The complexity of the promise constraint satisfaction problem is largely unknown, even for symmetric and , exc…
Linearly ordered colourings of hypergraphs
Tamio-Vesa Nakajima, Stanislav Živný
A linearly ordered (LO) -colouring of an -uniform hypergraph assigns an integer from to every vertex so that, in every edge, the (multi)set of colours has…