A Boolean predicate A is defined to be promise-useful if PCSP(A,B) is tractable for some nontrivial Boolean predicate B and otherwise it is promise-useless. We initiate investigations of this notion and derive sufficient conditions for both promise-usefulness and promise-uselessness (assuming P ≠ NP). While we do not obtain a complete characterization, our conditions are sufficient to classify all predicates of arity at most 4 and almost all predicates of arity 5. We also derive asymptotic results to show that for large arities a vast majority of all predicates are promise-useless. Our results are primarily obtained by a thorough study of the “Promise-SAT” problem, in which we are given a k-SAT instance with the promise that there is a satisfying assignment for which the literal values of each clause satisfy some additional constraint. The algorithmic results are based on the basic LP + affine IP algorithm of Brakensiek et al. (SICOMP, 2020) while we use a number of novel criteria to establish NP-hardness.

This thesis contains three papers on approximation algorithms and inapproximability results. Paper A contains NP-hardness inapproximability results for the Max-2Lin(2) problem, where 2Lin(2) refers to a system of linear equations modulo $2$ with two variables per equation. Paper B gives an approximation algorithm for the recently introduced linearly ordered hypergraph coloring problem. Before our paper, the best known approximation algorithm was able to color a $2$-colorable $3$-uniform hypergraph with $n$ nodes using $O(\sqrt[5]n)$ colors. But our approximation algorithm is able to do it in only $\log_2(n)$ colors, breaking the $n^{O(1)}$ barrier. Paper C introduces two completely new concepts called promise useful and promise useless for Promise Constraint Satisfaction Problems (PCSPs). The paper also contains a survey of essential results related to these two concepts. The hope is that these concepts will lead to a new direction of research for PCSPs.

Denna avhandling innehåller tre artiklar om approximationsalgoritmer och resultat om icke-approximabilitet. Artikel A innehåller NP-svårhetsresultat om icke-approximabilitet för Max-2Lin(2), där 2Lin(2) syftar på ett linjärt ekvationssystem modulo 2 med två variabler per ekvation. Artikel B innehåller en approximationsalgoritm för linjärt ordnad hypergraf-färgning. Rekordet innan Artikel B var en approximationsalgoritm som klarade av att färlägga en $2$-färgbar $3$-uniform hypergraf med $n$ noder med $O(\sqrt[5]n)$ färger. Men vår approximationsalgoritm använder endast $\log_2(n)$ färger, vilket slår $n^{O(1)}$-barriären. Artikel C introducerar två helt nya begrepp, kallade ``promise useful'' och ``promise useless'', för så kallade Promise Constraint Satisfaction Problems (PCSPer). Artikeln innehåller också en undersökning över viktiga resultat relaterade till dessa två begrepp. Förhoppningen är att begreppen kommer att leda till nya forskningsinriktningar för PCSPer.

A linearly ordered (LO) k-colouring of a hypergraph assigns to each vertex a colour from the set {0, 1, . . ., k − 1} in such a way that each hyperedge has a unique maximum element. Barto, Batistelli, and Berg conjectured that it is NP-hard to find an LO k-colouring of an LO 2-colourable 3-uniform hypergraph for any constant k ≥ 2 [STACS’21] but even the case k = 3 is still open. Nakajima and Živný gave polynomial-time algorithms for finding, given an LO 2-colourable 3-uniform hypergraph, an LO colouring with O*(√n) colours [ICALP’22] and an LO colouring with O*(√3 n) colours [ACM ToCT’23]. Very recently, Louis, Newman, and Ray gave an SDP-based algorithm with O*(√5 n) colours. We present two simple polynomial-time algorithms that find an LO colouring with O(log2(n)) colours, which is an exponential improvement.

In the Max-2Lin(2) problem you are given a system of equations on the form xi + xj ≡ b (mod 2), and your objective is to find an assignment that satisfies as many equations as possible. Let c ∈ [0.5, 1] denote the maximum fraction of satisfiable equations. In this paper we construct a curve s(c) such that it is NP-hard to find a solution satisfying at least a fraction s of equations. This curve either matches or improves all of the previously known inapproximability NP-hardness results for Max-2Lin(2). In particular, we show that if c ≥ 0.9232 then 1−1−s(cc) > 1.48969, which improves the NP-hardness inapproximability constant for the min deletion version of Max-2Lin(2). Our work complements the work of O’Donnell and Wu that studied the same question assuming the Unique Games Conjecture. Similar to earlier inapproximability results for Max-2Lin(2), we use a gadget reduction from the (2k − 1)-ary Hadamard predicate. Previous works used k ranging from 2 to 4. Our main result is a procedure for taking a gadget for some fixed k, and use it as a building block to construct better and better gadgets as k tends to infinity. Our method can be used to boost the result of both smaller gadgets created by hand (k = 3) or larger gadgets constructed using a computer (k = 4).

A linearly ordered (LO) k-colouring of a hypergraph assigns to each vertex a colour from the set {0,1,…,k−1} in such a way that each hyperedge has a unique maximum element. Barto, Batistelli, and Berg conjectured that it is NP-hard to find an LO k-colouring of an LO 2-colourable 3-uniform hypergraph for any constant k≥2 [STACS'21] but even the case k=3 is still open. Nakajima and Živný gave polynomial-time algorithms for finding, given an LO 2-colourable 3-uniform hypergraph, an LO colouring with O∗(n−−√) colours [ICALP'22] and an LO colouring with O∗(n−−√3) colours [ACM ToCT'23]. Very recently, Louis, Newman, and Ray gave an SDP-based algorithm with O∗(n−−√5) colours [FSTTCS'24]. We present two simple polynomial-time algorithms that find an LO colouring with O(log2(n)) colours, which is an exponential improvement. 

A Boolean predicate A is defined to be promise-useful if PCSP(A B)  is tractable for some non-trivial B and otherwise it is promise-useless. We initiate investigations of this notion and derive sufficient conditions for both promise-usefulness and promise-uselessness (assuming P is not equal to NP ). While we do not obtain a complete characterization, our conditions are sufficient to classify all predicates of arity at most 4 and almost all predicates of arity 5. We also derive asymptotic results to show that for large arities a vast majority of all predicates are promise-useless.

Our results are primarily obtained by a thorough study of the ``Promise-SAT'' problem, in which we are given a k-SAT instance with the promise that there is a satisfying assignment for which the literal values of each clause satisfy some additional constraint.

The algorithmic results are based on the basic LP + affine IP algorithm of Brakensiek et al.~(SICOMP, 2020) while we use a number of novel criteria to establish NP-hardness.