In the recent years, significant progress has been made in explaining apparent hardness of improving over naive solutions for many fundamental polynomially solvable problems. This came in the form of conditional lower bounds -- reductions from a problem assumed to be hard. These include 3SUM, All-Pairs Shortest Paths, SAT and Orthogonal Vectors, and others. In the $(\min,+)$-convolution problem, the goal is to compute a sequence $(c[i])^{n-1}_{i=0}$, where $c[k] = $ $\min_{i=0,\ldots,k} $ $\{a[i] $ $+$ $b[k-i]\}$, given sequences $(a[i])^{n-1}_{i=0}$ and $(b[i])_{i=0}^{n-1}$. This can easily be done in $O(n^2)$ time, but no $O(n^{2-\varepsilon})$ algorithm is known for $\varepsilon > 0$. In this paper we undertake a systematic study of the $(\min,+)$-convolution problem as a hardness assumption. As the first step, we establish equivalence of this problem to a group of other problems, including variants of the classic knapsack problem and problems related to subadditive sequences. The $(\min,+)$-convolution has been used as a building block in algorithms for many problems, notably problems in stringology. It has also already appeared as an ad hoc hardness assumption. We investigate some of these connections and provide new reductions and other results. We also explain why replacing this assumption with SETH might not be possible for some problems.

We consider four well-studied NP-complete packing/covering problems on graphs: Feed- back Vertex Set in Tournaments (FVST), Cluster Vertex Deletion (CVD), Triangle Packing in Tournaments (TPT) and Induced P_3-Packing. For these four problems kernels with O(k^2) vertices have been known for a long time. In fact, such kernels can be obtained by interpreting these problems as finding either a packing of k pairwise disjoint sets of size 3 (3-Set Packing) or a hitting set of size at most k for a family of sets of size at most 3 (3-Hitting Set). In this paper, we give the first kernels for FVST, CVD, TPT and Induced P_3-Packing with a subquadratic number of vertices. Specifically, we obtain the following results. (a) FVST admits a kernel with O(k^1.5 ) vertices. (b) CVD admits a kernel with O(k^(5/3)) vertices. (c) TPT admits a kernel with O(k^(1.5) ) vertices. (d) Induced P_3-Packing admits a kernel with O(k^(5/3 ) vertices. Our results resolve an open problem from WorKer 2010 on the existence of kernels with O(k^(2-e)) vertices for FVST and CVD. All of our results are based on novel uses of old and new expansion lemmas, and a weak form of crown decomposition where (i) almost all of the head is used by the solution (as opposed to all), (ii) almost none of the crown is used by the solution (as opposed to none), and (iii) if H is removed from G, then there is almost no interaction between the head and the rest (as oppose

In this paper, we develop an $O((m \log k) {\rm MSF} (n,m,1))$-time algorithm to find a half-integral node-capacitated multiflow of the maximum total flow-value in a network with $n$ nodes, $m$ edges, and $k$ terminals, where ${\rm MSF} (n',m',\gamma)$ denotes the time complexity of solving the maximum submodular flow problem in a network with $n'$ edges, $m'$ edges, and the complexity $\gamma$ of computing the exchange capacity of the submodular function describing the problem. % By using Fujishige-Zhang algorithm for submodular flow, we can find a maximum half-integral multiflow in $O(m n^3 \log k)$ time. This is the first combinatorial strongly polynomial time algorithm for this problem. % Our algorithm is designed on the basis of a developing theory of discrete convex functions on certain graph structures. % Applications include ``ellipsoid-free" combinatorial implementations of a 2-approximation algorithm for the minimum node-multiway cut problem by Garg, Vazirani, and Yannakakis.