A recent trend in parameterized algorithms is the application of polytope tools (specifically, LP-branching) to FPT algorithms (e.g., , 2011; , 2012). However, although interesting results have been achieved, the methods require the underlying polytope to have very restrictive properties (half-integrality and persistence), which are known only for few problems (essentially Vertex Cover (Nemhauser and Trotter, 1975) and Node Multiway Cut (, 1994)). Taking a slightly different approach, we view half-integrality as a relaxation of a problem, e.g., a relaxation of the search space from @math to @math such that the new problem admits a polynomial-time exact solution. Using tools from CSP (in particular Thapper and Z ivn 'y, 2012) to study the existence of such relaxations, we provide a much broader class of half-integral polytopes with the required properties, unifying and extending previously known cases. In addition to the insight into problems with half-integral relaxations, our results yield a range of new and improved FPT algorithms, including an @math -time algorithm for node-deletion Unique Label Cover with label set @math and an @math -time algorithm for Group Feedback Vertex Set, including the setting where the group is only given by oracle access. All these significantly improve on previous results. The latter result also implies the first single-exponential time FPT algorithm for Subset Feedback Vertex Set, answering an open question of (2012). Additionally, we propose a network flow-based approach to solve some cases of the relaxation problem. This gives the first linear-time FPT algorithm to edge-deletion Unique Label Cover.
This paper presents a combinatorial polynomial-time algorithm for minimizing submodular functions, answering an open question posed in 1981 by Grotschel, Lovasz, and Schrijver. The algorithm employs a scaling scheme that uses a flow in the complete directed graph on the underlying set with each arc capacity equal to the scaled parameter. The resulting algorithm runs in time bounded by a polynomial in the size of the underlying set and the length of the largest absolute function value. The paper also presents a strongly polynomial version in which the number of steps is bounded by a polynomial in the size of the underlying set, independent of the function values. Abstract We define a class of monotone integer programs with constraints that involve up to three variables each. A generic constraint in such integer program is of the form ax − by ⩽ z + c , where a and b are nonnegative and the variable z appears only in that constraint. We devise an algorithm solving such problems in time polynomial in the length of the input and the range of variables U . The solution is obtained from a minimum cut on a graph with O( nU ) nodes and O( mU ) arcs where n is the number of variables of the types x and y and m is the number of constraints. Our algorithm is also valid for nonlinear objective functions. Nonmonotone integer programs are optimization problems with constraints of the type ax + by ⩽ z + c without restriction on the signs of a and b . Such problems are in general NP-hard. We devise here an algorithm, relying on a transformation to the monotone case, that delivers half integral superoptimal solutions in polynomial time. Such solutions provide bounds on the optimum value that can only be superior to bounds provided by linear programming relaxation. When the half integral solution can be rounded to an integer feasible solution, this is a 2-approximate solution. In that the technique is a unified 2-approximation technique for a large class of problems. The results apply also for general integer programming problems with worse approximation factors that depend on a quantifier measuring how far the problem is from the class of problems we describe. The algorithm described here has a wide array of problem applications. An additional important consequence of our results is that nonmonotone problems in the framework are MAX SNP-hard and at least as hard to approximate as vertex cover. Problems that are amenable to the analysis provided here are easily recognized. The analysis itself is entirely technical and involves manipulating the constraints and transforming them to a totally unimodular system while losing no more than a factor of 2 in the integrality. We report new results on the complexity of the valued constraint satisfaction problem (VCSP). Under the unique games conjecture, the approximability of finite-valued VCSP is fairly well-understood. However, there is yet no characterisation of VCSPs that can be solved exactly in polynomial time. This is unsatisfactory, since such results are interesting from a combinatorial optimisation perspective; there are deep connections with, for instance, submodular and bisubmodular minimisation. We consider the Min and Max CSP problems (i.e. where the cost functions only attain values in 0,1 ) over four-element domains and identify all tractable fragments. Similar classifications were previously known for two- and three-element domains. In the process, we introduce a new class of tractable VCSPs based on a generalisation of submodularity. We also extend and modify a graph-based technique by Kolmogorov and Zivny (originally introduced by Takhanov) for efficiently obtaining hardness results in our setting. This allow us to prove the result without relying on computer-assisted case analyses (which otherwise are fairly common when studying the complexity and approximability of VCSPs.) The hardness results are further simplified by the introduction of powerful reduction techniques. 