An FPT Algorithm Beating 2-Approximation for k-Cut, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy
January 24, 2018 (GHC 6115 )

An FPT Algorithm Beating 2-Approximation for k-Cut:

In the k-cut problem, we are given an edge-weighted graph $G$ and an integer $k$, and have to remove a set of edges with minimum total weight so that $G$ has at least $k$ connected components. Prior work on this problem gives, for all $h \in [2,k]$, a $(2-h/k)$-approximation algorithm for $k$-cut that runs in time $n^{O(h)}$. Hence to get a $(2 - \eps)$-approximation algorithm for some absolute constant $\eps$, the best runtime using prior techniques is $n^{O(k\eps)}$. Moreover, it was recently shown that getting a $(2 - \eps)$-approximation for general $k$ is NP-hard, assuming the Small Set Expansion Hypothesis.

If we use the size of the cut as the parameter, an FPT algorithm to find the exact k-cut is known, but solving the k-cut problem exactly is $W[1]$-hard if we parameterize only by the natural parameter of $k$. An immediate question is: \emph{can we approximate k-cut better in FPT-time, using $k$ as the parameter?}

We answer this question positively. We show that for some absolute constant $\eps > 0$, there exists a $(2 - \eps)$-approximation algorithm that runs in time $2^{O(k^6)} \cdot \tilde{O} (n^4)$. This is the first FPT algorithm that is parameterized only by $k$ and strictly improves the $2$-approximation.

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy:

A classic result of Schaefer [STOC, 1978] classifies all constraint satisfaction problems (CSPs) over the Boolean domain to be either in P or NP-hard. This paper considers a promise-problem variant of CSPs called PCSPs. Many problems such as approximate graph and hypergraph coloring, the (2+ϵ)-SAT problem due to Austrin, Guruswami, and H{\aa}stad [SIAM Journal on Computing, 2017], and the digraph homomorphism problem can be placed in this framework.

This paper is motivated by the pursuit of understanding the computational complexity of Boolean PCSPs, determining which PCSPs are polynomial-time tractable or NP-hard. As our main result, we show that PCSPs exhibits a dichotomy (it is either polynomial-time tractable or NP-hard) when the clauses are symmetric and allow for negations of variables. In particular, we show that every such polynomial-time tractable instance can be solved via either Gaussian elimination over F_2 or a linear programming relaxation. We achieve our dichotomy theorem by extending the weak polymorphism framework of AGH which itself is a generalization of the algebraic approach used by polymorphisms to study CSPs. In both the algorithm and hardness portions of our proof, we incorporate new ideas and techniques not utilized in the CSP case.

Joint work with Venkatesan Guruswami.