Hardness of Approximating Constraint Satisfaction Problems and Their Variants in Presence of Additional Structural Assumptions

QC 2023-05-08

Abstract

This thesis studies how the approximability of some fundamental computational problems is affected by some additional requirements on the structure of the inputs. The problems studied in this thesis belong or are closely related to constraint satisfaction problems (CSPs), which are considered to be one of the most fundamental problems in theoretical computer science.

The first class of problems studied in this thesis consists of some Boolean CSPs with cardinality constraints. A cardinality constraint for an instance of a Boolean CSP restricts assignments to have a certain number of variables assigned to 1 and 0. Assuming the Unique Games Conjecture, we show that Max-Cut with cardinality constraints is hard to approximate within approximately 0.858, and that Max-2-Sat with cardinality constraints is hard to approximate within approximately 0.929. The same inapproximability ratio as for cardinality constrained Max-2-Sat is obtained for the cardinality-constrained Vertex Cover problem, known as Max-k-VC.

We also examine regular constraint satisfaction problems where each variable in an instance has the same number of occurrences. We investigate approximability of such problems and show that for any CSP Λ, the existence of an α-approximation algorithm for regular Max-CSP Λ implies the existence of an (α − o(1))-approximation algorithm for weighted Max-CSP Λ for which the regularity of instances is not imposed. We also give an analogous result for Min-CSPs. In particular, if one is not interested in lower-order terms, we show that the study of the approximability of CSPs can be conducted solely on regular instances.

We also consider approximability of Max-3-Lin problems over non-Abelian groups in a universal factor graph setting. The factor graph of an instance with n variables and m constraints is the bipartite graph between [m] and [n], in which edges connect constraints with the variables they contain. The universal factor graph setting assumes that a factor graph for an instance is fixed for each input size. Building on the previous works, we show optimal inapproximability of Max-3-Lin problems over non-Abelian groups in the universal factor graph setting, both in the case of perfect and almost perfect completeness. We also show that these hardness results apply in the setting in which linear equations in the Max-3-Lin  problem are restricted  to the form x · y · z = g, where x, y, z are variables and $g$ is a group element, in contrast to previous works where constants have appeared on the left side of the equations as well.

Finally, we study the approximability of the Minimum Sum Vertex Cover problem, in which we are given a graph as an input and the goal is to find anordering of vertices that minimizes the total cover time of edges. An edge is covered when one of its endpoints is visited in an ordering, and the covertime for the edge is exactly the time that the endpoint is visited.

In this work, we give the first explicit hardness of approximation result and show that Minimum Sum Vertex Cover can not be approximated below 1.0748, assuming the Unique Games Conjecture. Furthermore, we study Minimum Sum Vertex Cover on regular graphs and demonstrate an inapproximability ratio of 1.0157. By revisiting an algorithm introduced by Feige, Lov\'{a}sz, and Tetali, we also show approximability within 1.225 for regular graphs.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-326609