Hardness from Densest Subgraph Conjectures

Abstract

Karp's seminal paper on NP-Completeness provided computer scientists with a toolkit for showing computational hardness, conditioned on a complexity theoretic conjecture, for a wide variety of optimization problems. However, the techniques used in his paper say little about the hardness of approximating the optimal objective values of these problems. While researchers have since managed to find tight bounds on the approximability of some of these NP-hard problems, many others still have embarrassingly large gaps between their known upper and lower limits of approximation.

To fill in these gaps, researchers have posed myriad new complexity theoretic conjectures that entail stronger lower bounds at the expense of more demanding hypotheticals. One class of conjectures focuses on the approximability of the Densest k-Subgraph (DkS) problem. Namely, the conjectured hardness of both adversarial and average-case variants of DkS has been shown to imply stronger hardness for many problems for which good approximation algorithms have proven elusive.

In this dissertation, we study a variety of problems, each of which can have their hardness tied back to that of DkS. We describe techniques for proving stronger hardness results conditioned on both the known and the conjectured hardness of DkS. We show how previous results on DkS imply stronger lower bounds on "MinRep-hard" problems, as well as a simple technique for converting many proofs of MinRep-hardness into proofs of DkS-hardness. Using this and other techniques, we show DkS hardness for problems such as Target Set Selection, Minimum Monotone Satisfying Assignment, Min-Cost Colored Cut, Network Flow Interdiction, and Densest k-Common Subgraph, among others. In the case of Target Set Selection and Monotone Minimum Satisfying Assignment, we show how to obtain substantially stronger lower bounds by exploiting the self-similar structure of instances conjectured to be average-case-hard. We introduce the Middlebox Routing-class of problems, and show show exact, approximation, and hardness results for its member problems. We provide an O(sqrt(n)) approximation algorithm for Min k-Union, and discuss both approximation and hardness results for Densest Common Subgraph variants.