Search

We prove that Multicut in directed graphs, parameterized by the size of the cutset, is W[1]-hard and hence unlikely to be fixed-parameter tractable even if restricted to instances with only four terminal pairs. This negative result almost completely resolves one of the central open problems in the area of parameterized complexity of graph separation problems, posted originally by Marx and Razgon [SIAM J. Comput. 43(2):355--388 (2014)], leaving only the case of three terminal pairs open. The case of two terminal pairs was shown to be FPT by Chitnis et al. [SIAM J. Comput. 42(4):1674--1696 (2013)]. Our gadget methodology also allows us to prove W[1]-hardness of the Steiner Orientation problem parameterized by the number of terminal pairs, resolving an open problem of Cygan, Kortsarz, and Nutov [SIAM J. Discrete Math. 27(3):1503-1513 (2013)].

Strip packing is a classical packing problem, where the goal is to pack a set of rectangular objects into a strip of a given width, while minimizing the total height of the packing. The problem has multiple applications, for example, in scheduling and stock-cutting, and has been studied extensively. When the dimensions of the objects are allowed to be exponential in the total input size, it is known that the problem cannot be approximated within a factor better than 3/2, unless P= NP. However, there was no corresponding lower bound for polynomially bounded input data. In fact, Nadiradze and Wiese [SODA 2016] have recently proposed a (1.4 + ε)-approximation algorithm for this variant, thus showing that strip packing with polynomially bounded data can be approximated better than when exponentially large values are allowed in the input. Their result has subsequently been improved to a (4/3 + ε)-approximation by two independent research groups [FSTTCS 2016, WALCOM 2017]. This raises a question whether strip packing with polynomially bounded input data admits a quasi-polynomial time approximation scheme, as is the case for related two-dimensional packing problems like maximum independent set of rectangles or two-dimensional knapsack. In this article, we answer this question in negative by proving that it is NP-hard to approximate strip packing within a factor better than 12/11, even when restricted to polynomially bounded input data. In particular, this shows that the strip packing problem admits no quasi-polynomial time approximation scheme, unless NP} ⊑ DTIME(2polylog (n)).

This work further explores the applications of co-nondeterminism for showing kernelization lower bounds. The only known example prior to this work excludes polynomial kernelizations for the so-called Ramsey problem of finding an independent set or a clique of at least kvertices in a given graph [Kratsch 2012]. We study the more general problem of finding induced subgraphs on kvertices fulfilling some hereditary property Π, called Π-Induced Subgraph. The problem is NP-hard for all nontrivial choices of Π by a classic result of Lewis and Yannakakis [1980]. The parameterized complexity of this problem was classified by Khot and Raman [2002] depending on the choice of Π. The interesting cases for kernelization are for Π containing all independent sets and all cliques, since the problem is trivially polynomial time solvable or W[1]-hard otherwise.Our results are twofold. Regarding Π-Induced Subgraph, we show that for a large choice of natural graph properties Π, including chordal, perfect, cluster, and cograph, there is no polynomial kernel with respect to k. This is established by two theorems, each one capturing different (but not necessarily exclusive) sets of properties: one using a co-nondeterministic variant of OR-cross-composition and one by a polynomial parameter transformation from Ramsey.Additionally, we show how to use improvement versions of NP-hard problems as source problems for lower bounds, without requiring their NP-hardness. For example, for Π-Induced Subgraph our compositions may assume existing solutions of size k--1. This follows from the more general fact that source problems for OR-(cross-)compositions need only be NP-hard under co-nondeterministicreductions. We believe this to be useful for further lower-bound proofs, for example, since improvement versions simplify the construction of a disjunction (OR) of instances required in compositions. This adds a second way of using co-nondeterminism for lower bounds.

The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework of parameterized complexity. In this article, we show that, unless the polynomial hierarchy collapses to its third level, the following parameterized problems do not admit a polynomial-time preprocessing algorithm that reduces the size of an instance to polynomial in the parameter: ---Edge Clique Cover, parameterized by the number of cliques, ---Directed Edge/Vertex Multiway Cut, parameterized by the size of the cutset, even in the case of two terminals, ---Edge/Vertex Multicut, parameterized by the size of the cutset, and ---k-Way Cut, parameterized by the size of the cutset.

We introduce a concept of parameterizing a problem above the optimum solution of its natural linear programming relaxation and prove that the node multiway cut problem is fixed-parameter tractable (FPT) in this setting. As a consequence we prove that node multiway cut is FPT, when parameterized above the maximum separating cut, resolving an open problem of Razgon. Our results imply O*(4k) algorithms for vertex cover above maximum matching and almost 2-SAT as well as an O*(2k) algorithm for node multiway cut with a standard parameterization by the solution size, improving previous bounds for these problems.