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.
Submodular and bisubmodular functions also occur as rank functions of, respectively, matroids @cite_31 and delta-matroids @cite_11 ; there are also connections to polytope theory (e.g., @cite_50 ). Similar, but less well-explored connections exist for @math -submodular functions; see the theory of multi-matroids @cite_34 @cite_19 @cite_27 @cite_32 , and the polytope connection given by Huber and Kolmogorov @cite_53 .
@cite_53 @cite_32 @cite_19 @cite_27 @cite_50 @cite_31 @cite_34 @cite_11
1930126570 1987044417 1501742082 1972360724 2066894529 2309721867 2033956728
In this paper we investigate k-submodular functions. This natural family of discrete functions includes submodular and bisubmodular functions as the special cases k=1 and k=2 respectively. In particular we generalize the known Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts that the minimum of the (bi)submodular function can be found by solving a maximization problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron, prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm to construct the vertices of the polyhedron. Abstract This paper completes the series A. Bouchet, Multimatroids I, SIAM J. Disc. Math.; A. Bouchet, Multimatroid II. Minors and connectivity; A. Bouchet, Multimatroids III. Tightness, fundamental graphs and pivotings, devoted to the introduction of multimatroids. Here we define a notion of linear representation that encompasses the isotropic systems and the linear representations of matroids and delta-matroids. We show that every Eulerian multimatroid is representable with a symplectic vector space over GF(2). Finally we adapt the construction to symplectic matroids. A multimatroid is a combinatorial structure that encompasses matroids, delta-matroids and isotropic systems. This structure has been introduced to unify a theorem of Edmonds on the coverings of a matroid by independent sets and a theorem of Jackson on the existence of pairwise compatible Euler tours in a 4-regular graph. Here we investigate some basic concepts and properties related with multimatroids: matroid orthogonality, minor operations and connectivity. This paper continues the study of multimatroids. Here we introduce the subclass of tight multimatroids, which contains the liftings of even delta-matroids, the 3-matroids derived from isotropic systems, the Eulerian 3-matroids associated to 4-regular graphs and the Eulerian 2-matroids associated to evenly directed 4-regular graphs. The local properties of a tight multimatroid in the vicinity of a base are reflected by a fundamental graph, as in matroid theory. We describe how the fundamental graph is transformed when the base is modified. As an application we derive some connectivity properties of tight multimatroids. This paper relates an axiomatic generalization of matroids, called a jump system, to polyhedra arising from bisubmodular functions. Unlike the case for usual submodularity, the points of interest are not all the integral points in the relevant polyhedron but form a subset of them. However, it is shown that the convex hull of the set of points of a jump system is a bisubmodular polyhedron, and that the integral points of an integral bisubmodular polyhedron determine a (special) jump system. The authors prove addition and composition theorems for jump systems, which have several applications for delta-matroids and matroids. Multimatroids are combinatorial structures that generalize matroids and arise in the study of Eulerian graphs. We prove, by means of an efficient algorithm, a covering theorem for multimatroids. This theorem extends Edmonds' covering theorem for matroids. It also generalizes a theorem of Jackson on the Euler tours of a 4-regular graph.