We provide the first non-trivial approximation algorithm for the fundamental directed feedback vertex set (DFVS) problem in the class of quasi-transitive digraphs. This class of digraphs encompasses both dense and sparse classes of digraphs, for which specialized DFVS algorithms were proposed in the literature, like tournaments or transitive orientations of bounded treewidth graphs. Our approximation algorithm can handle both dense graphs, as well as sparse graphs, by a single approach, which is based on carefully analysing the solutions to a linear programming relaxation of DFVS. It also handles the node-weighted DFVS problem, for which it computes a 9/4-approximation in polynomial time. Along the way, we improve and simplify the best-known deterministic polynomial-time approximation algorithms for DFVS in tournaments (Cai et al., SICOMP 2001; Mnich et al., ESA 2016).

We study the problem of partitioning a set of n objects in a metric space into k clusters V₁,...,V_k. The quality of the clustering is measured by considering the vector of cluster costs and then minimizing some monotone symmetric norm of that vector (in particular, this includes the 𝓁_p-norms). For the costs of the clusters we take the weight of a minimum-weight spanning tree on the objects in V_i, which may serve as a proxy for the cost of traversing all objects in the cluster, for example in the context of Multirobot Coverage as studied by Zheng, Koenig, Kempe, Jain (IROS 2005), but also as a shape-invariant measure of cluster density similar to Single-Linkage Clustering. This problem has been studied by Even, Garg, Könemann, Ravi, Sinha (Oper. Res. Lett., 2004) for the setting of minimizing the weight of the largest cluster (i.e., using 𝓁_∞) as Min-Max Tree Cover, for which they gave a constant-factor approximation algorithm. We provide a careful adaptation of their algorithm to compute solutions which are approximately optimal with respect to all monotone symmetric norms simultaneously, and show how to find them in polynomial time. In fact, our algorithm is purely combinatorial and can process metric spaces with 10,000 points in less than a second. As an extension, we also consider the case where instead of a target number of clusters we are provided with a set of depots in the space such that every cluster should contain at least one such depot. One can consider these as the fixed starting points of some agents that will traverse all points of a cluster. For this setting also we are able to give a polynomial-time algorithm computing a constant-factor approximation with respect to all monotone symmetric norms simultaneously. To show that the algorithmic results are tight up to the precise constant of approximation attainable, we also prove that such clustering problems are already APX-hard when considering only one single 𝓁_p norm for the objective.

We present a new $(\frac32+\frac1{\mathrm{e}})$-approximation algorithm for the Ordered Traveling Salesperson Problem (Ordered TSP). Ordered TSP is a variant of the classical metric Traveling Salesperson Problem (TSP) where a specified subset of vertices needs to appear on the output Hamiltonian cycle in a given order, and the task is to compute a cheapest such cycle. Our approximation guarantee of approximately $1.868$ holds with respect to the value of a natural new linear programming (LP) relaxation for Ordered TSP. Our result significantly improves upon the previously best known guarantee of $\frac52$ for this problem and thereby considerably reduces the gap between approximability of Ordered TSP and metric TSP. Our algorithm is based on a decomposition of the LP solution into weighted trees that serve as building blocks in our tour construction.

This paper focuses on kernelization algorithms for the fundamental Knapsack problem. A kernelization algorithm (or kernel) is a polynomial-time reduction from a problem onto itself, where the output size is bounded by a function of some problem-specific parameter. Such algorithms provide a theoretical model for data reduction and preprocessing and are central in the area of parameterized complexity. In this way, a kernel for Knapsack for some parameter $k$ reduces any instance of Knapsack to an equivalent instance of size at most $f(k)$ in polynomial time, for some computable function $f(\cdot)$. When $f(k)=k^{O(1)}$ then we call such a reduction a polynomial kernel. Our study focuses on two natural parameters for Knapsack: The number of different item weights $w_{\#}$, and the number of different item profits $p_{\#}$. Our main technical contribution is a proof showing that Knapsack does not admit a polynomial kernel for any of these two parameters under standard complexity-theoretic assumptions. Our proof discovers an elaborate application of the standard kernelization lower bound framework, and develops along the way novel ideas that should be useful for other problems as well. We complement our lower bounds by showing the Knapsack admits a polynomial kernel for the combined parameter $w_{\#}+p_{\#}$.

We study the fundamental scheduling problem 1|r_j|∑ w_j U_j: schedule a set of n jobs with weights, processing times, release dates, and due dates on a single machine, such that each job starts after its release date and we maximize the weighted number of jobs that complete execution before their due date. Problem 1|r_j|∑ w_j U_j generalizes both Knapsack and Partition, and the simplified setting without release dates was studied by Hermelin et al. [Annals of Operations Research, 2021] from a parameterized complexity viewpoint. Our main contribution is a thorough complexity analysis of 1|r_j|∑ w_j U_j in terms of four key problem parameters: the number p_# of processing times, the number w_# of weights, the number d_# of due dates, and the number r_# of release dates of the jobs. 1|r_j|∑ w_j U_j is known to be weakly para-NP-hard even if w_#+d_#+r_# is constant, and Heeger and Hermelin [ESA, 2024] recently showed (weak) 𝖶[1]-hardness parameterized by p_# or w_# even if r_# is constant. Algorithmically, we show that 1|r_j|∑ w_j U_j is fixed-parameter tractable parameterized by p_# combined with any two of the remaining three parameters w_#, d_#, and r_#. We further provide pseudo-polynomial XP-time algorithms for parameter r_# and d_#. To complement these algorithms, we show that 1|r_j|∑ w_j U_j is (strongly) 𝖶[1]-hard when parameterized by d_#+r_# even if w_# is constant. Our results provide a nearly complete picture of the complexity of 1|r_j|∑ w_j U_j for p_#, w_#, d_#, and r_# as parameters, and extend those of Hermelin et al. [Annals of Operations Research, 2021] for the problem 1||∑ w_j U_j without release dates.

The fundamental Sparsest Cut problem takes as input a graph G together with edge capacities and demands and seeks a cut that minimizes the ratio between the capacities and demands across the cuts. For n -vertex graphs G of treewidth k , Chlamtáč, Krauthgamer, and Raghavendra (APPROX’10) presented an algorithm that yields a factor- \(2^{2^k}\) approximation in time \(2^{O(k)} \cdot n^{O(1)}\) . Later, Gupta, Talwar, and Witmer (STOC’13) showed how to obtain a 2-approximation algorithm with a blown-up runtime of \(n^{O(k)}\) . An intriguing open question is whether one can simultaneously achieve the best out of the aforementioned results, that is, a factor-2 approximation in time \(2^{O(k)} \cdot n^{O(1)}\) . In this article, we make significant progress towards this goal via the following results: (i) A factor- \(O(k^2)\) approximation that runs in time \(2^{O(k)} \cdot n^{O(1)}\) , directly improving the work of Chlamtáč et al. while keeping the runtime single-exponential in k . (ii) For any \(\varepsilon \in (0,1]\) , a factor- \(O(1/\varepsilon ^2)\) approximation whose runtime is \(2^{O(k^{1+\varepsilon }/\varepsilon)} \cdot n^{O(1)}\) , implying a constant-factor approximation whose runtime is nearly single-exponential in k and a factor- \(O(\log ^2 k)\) approximation in time \(k^{O(k)} \cdot n^{O(1)}\) . Key to these results is a new measure of a tree decomposition that we call combinatorial diameter , which may be of independent interest.

Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition's width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth (sd). Here, sd is a bounded-depth analogue of cliquewidth, in the same way as td is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. Precisely, we prove that on $n$-vertex graphs equipped with a tree-model (a decomposition notion underlying sd) of depth $d$ and using $k$ labels, we can solve - Independent Set in time $2^{O(dk)}\cdot n^{O(1)}$ using $O(dk^2\log n)$ space; - Max Cut in time $n^{O(dk)}$ using $O(dk\log n)$ space; and - Dominating Set in time $2^{O(dk)}\cdot n^{O(1)}$ using $n^{O(1)}$ space via a randomized algorithm. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of IS the exponent of the parametric factor in the time complexity has to grow with $d$ if one wishes to keep the space complexity polynomial.

We study the d-DIMENSIONAL VECTOR BIN PACKING ($d \mathbf{V B P})$ problem, a generalization of BIN PACKING with central applications in resource allocation and scheduling. In $d \mathrm{VBP}$, we are given a set of items, each of which is characterized by a d-dimensional volume vector; the objective is to partition the items into a minimum number of subsets (bins), such that the total volume of items in each subset is at most 1 in each dimension. Our main result is an asymptotic approximation algorithm for d VBP that yields a ratio of $(1+\ln d-\chi(d)+\varepsilon)$ for all $d \in \mathbb{N}$ and any $\varepsilon\gt0$; here, $\chi(d)$ is some strictly positive function. This improves upon the best known asymptotic ratio of $(1+\ln d+\varepsilon)$ due to Bansal, Caprara and Sviridenko (SICOMP 2010) for any $d\gt3$. By slightly modifying our algorithm to include an initial matching phase and applying a tighter analysis, we obtain an asymptotic approximation ratio of $\left(\frac{4}{3}+\varepsilon\right)$ for the special case of $d=2$, thus substantially improving the previous best ratio of $\left(\frac{3}{2}+\varepsilon\right)$ due to Bansal, Eliáš and Khan (SODA 2016). Our algorithm iteratively solves a configuration LP relaxation for the residual instance (from previous iterations) and samples a small number of configurations based on the solution for the configuration LP. While iterative rounding was already used by Karmarkar and Karp (FOCS 1982) to establish their celebrated result for classic (one-dimensional) BIN PACKING, iterative randomized rounding is used here for the first time in the context of (VECTOR) BIN PACKING. Our results show that iterative randomized rounding is a powerful tool for approximating d VBP, leading to simple algorithms with improved approximation guarantees.

Shrinking hardware structures and decreasing operating voltages lead to an increasing number of transient hardware faults, which thus become a core problem to consider for safety-critical systems. Here, systematic fault injection (FI), where one program-under-test is systematically stressed with faults, provides an in-depth resilience analysis in the presence of faults. However, FI campaigns require many independent injection experiments and, combined, long run times, especially if we aim for a high coverage of the fault space. One cost factor is the forwarding phase, which is the time required to bring the system-under test into the fault-free state at injection time. One common technique to speed up the forwarding are checkpoints of the fault-free system state at fixed points in time. In this paper, we show that the placement of checkpoints has a significant influence on the required forwarding cycles, especially if we place faults non-uniformly on the time axis. For this, we discuss the checkpoint-selection problem in general, formalize it as a maximum-weight reward path problem in graphs, propose an ILP formulation and a dynamic programming algorithm that find the optimal solution, and provide a heuristic checkpoint-selection method based on a genetic algorithm. Applied to the MiBench benchmark suite, our approach consistently reduces the forward-phase cycles by at least 88 percent and up to 99.934 percent when placing 16 checkpoints.

Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs directly correlates with their support size, which is the minimum number of non-zero integer variables in an optimal solution. A hallmark result by Eisenbrand and Shmonin (Oper. Res. Lett., 2006) shows that any feasible integer linear program (ILP) has a solution with support size $s\leq 2m\cdot\log(4mΔ)$, where $m$ is the number of constraints, and $Δ$ is the largest coefficient in any constraint. Our main combinatorial result are improved support size bounds for ILPs. To improve granularity, we analyze for the largest $1$-norm $A_{\max}$ of any column of the constraint matrix, instead of $Δ$. We show a support size upper bound of $s\leq m\cdot(\log(3A_{\max})+\sqrt{\log(A_{\max})})$, by deriving a new bound on the -1 branch of the Lambert $\mathcal{W}$ function. Additionally, we provide a lower bound of $m\log(A_{\max})$, proving our result asymptotically optimal. Furthermore, we give support bounds of the form $s\leq 2m\cdot\log(1.46A_{\max})$. These improve upon the previously best constants by Aliev. et. al. (SIAM J. Optim., 2018), because all our upper bounds hold equally with $A_{\max}$ replaced by $\sqrt{m}Δ$. Using our combinatorial result, we obtain the fastest known approximation schemes (EPTAS) for the fundamental scheduling problem of makespan minimization of uniformly related machines ($Q\mid\mid C_{\max}$).

In the Many-visits Path TSP, we are given a set of $n$ cities along with their pairwise distances (or costs) $c(uv)$, and moreover each city $v$ comes with an associated positive integer request $r(v)$. The goal is to find a minimum-cost path, starting at city $s$ and ending at city $t$, that visits each city $v$ exactly $r(v)$ times. We present a $3/2$-approximation algorithm for the metric Many-visits Path TSP that runs in time polynomial in $n$ and polylogarithmic in the requests $r(v)$. Our algorithm can be seen as a generalization of the $3/2$-approximation algorithm for Path TSP by Zenklusen [ Proceedings of SODA, 2019, pp. 1539--1549], which answered a long-standing open problem by providing an efficient algorithm which matches the approximation guarantee of Christofides' algorithm from 1976 for metric TSP. One of the key components of our approach is a polynomial-time algorithm to compute a connected, degree-bounded multigraph of minimum cost in an undirected graph with edge costs. We tackle this problem by generalizing a fundamental result of Király, Lau, and Singh [ Combinatorica, 32 (2012), pp. 705--720] on the Minimum Bounded Degree Matroid Basis problem, and devise such an algorithm for generalized polymatroids, even allowing element multiplicities. Our result directly yields a $3/2$-approximation to the metric Many-visits TSP, as well as a $3/2$-approximation for the problem of scheduling classes of jobs with sequence-dependent setup times on a single machine so as to minimize the makespan.

A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph $G$ which intersects all copies of subgraphs $F$ from a fixed family $\mathcal F$. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTASs) for planar input graphs $G$, using a variety of techniques like the shifting technique [B. S. Baker, J. ACM, 41 (1994), pp. 153--180], bidimensionality [F. V. Fomin et al., Bidimensionality and EPTAS, in Proceedings of SODA 2011, ACM, New York, SIAM, Philadelphia, 2011, pp. 748--759], or connectivity domination [V. Cohen-Addad et al., Approximating connectivity domination in weighted bounded-genus graphs, in Proceedings of STOC 2016, ACM, New York, 2016, pp. 584--597]. These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the Even Cycle Transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini, Joret, and Pietropaoli [ Hitting diamonds and growing cacti, in Proceedings of IPCO 2010, Lecture Notes in Comput. Sci. 6080, Springer, Berlin, 2010, pp. 191--204] showed that the integrality gap of the standard covering LP relaxation is $\Theta(\log n)$, and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a $47/7\approx6.71$-approximation for ECT on node-weighted planar graphs, and an integrality gap upper bound of the same value for the standard LP relaxation on node-weighted planar graphs.

A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph G which intersects all copies of subgraphs F from a fixed family F. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTAS) for planar input graphs G, using a variety of techniques like the shifting technique (Baker, J. ACM 1994), bidimensionality (Fomin et al., SODA 2011), or connectivity domination (Cohen-Addad et al., STOC 2016). These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the even-cycle transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini et al. (IPCO 2010) showed that the integrality gap of the standard covering LP relaxation is Θ(log n), and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a 47/7 ≈ 6.71-approximation for ECT on node-weighted planar graphs, and an integrality gap of the same value for the standard LP relaxation on node-weighted planar graphs.

Kernelization is a general theoretical framework for preprocessing instances of NP-hard problems into (generally smaller) instances with bounded size, via the repeated application of data reduction rules. For the fundamental Max Cut problem, kernelization algorithms are theoretically highly efficient for various parameterizations. However, the efficacy of these reduction rules in practice—to aid solving highly challenging benchmark instances to optimality—remains entirely unexplored. We engineer a new suite of efficient data reduction rules that subsume most of the previously published rules, and demonstrate their significant impact on benchmark data sets, including synthetic instances, and data sets from the VLSI and image segmentation application domains. Our experiments reveal that current state-of-the-art solvers can be sped up by up to multiple orders of magnitude when combined with our data reduction rules. On social and biological networks in particular, kernelization enables us to solve four instances that were previously unsolved in a ten-hour time limit with state-of-the-art solvers; three of these instances are now solved in less than two seconds.

In the Directed Long Cycle Hitting Set} problem we are given a directed graph $G$, and the task is to find a set $S$ of at most $k$ vertices/arcs such that $G-S$ has no cycle of length longer than $\ell$. We show that the problem can be solved in time $2^{\mathcal O(\ell k^3\log k + k^5\log k\log\ell)}\cdot n^{\mathcal O(1)}$, that is, it is fixed-parameter tractable (FPT) parameterized by $k$ and $\ell$. This algorithm can be seen as a far-reaching generalization of the fixed-parameter tractability of {\sc Mixed Graph Feedback Vertex Set} [Bonsma and Lokshtanov WADS 2011], which is already a common generalization of the fixed-parameter tractability of (undirected) {\sc Feedback Vertex Set} and the {\sc Directed Feedback Vertex Set} problems, two classic results in parameterized algorithms. The algorithm requires significant insights into the structure of graphs without directed cycles length longer than $\ell$ and can be seen as an exact version of the approximation algorithm following from the Erd{ő}s-P{ó}sa property for long cycles in directed graphs proved by Kreutzer and Kawarabayashi [STOC 2015].

Abstract Stable matching problems with lower quotas are fundamental in academic hiring and ensuring operability of rural hospitals. Only few tractable (polynomial-time solvable) cases of stable matching with lower quotas have been identified; most such problems are $$\mathsf {NP}$$ NP -hard and also hard to approximate (Hamada et al. in Algorithmica 74(1):440–465, 2016). We therefore consider stable matching problems with lower quotas under a relaxed notion of tractability, namely fixed-parameter tractability. By cloning hospitals we focus on the case when all hospitals have upper quota equal to 1, which generalizes the setting of “arranged marriages” first considered by Knuth (Mariages stables et leurs relations avec d’autres problèmes combinatoires, Les Presses de l’Université de Montréal, Montreal, 1976). We investigate how a set of natural parameters, namely the maximum length of preference lists for men and women, the number of distinguished men and women, and the number of blocking pairs allowed determine the computational tractability of this problem. Our main result is a complete complexity trichotomy: for each choice of parameters we either provide a polynomial-time algorithm, or an $$\mathsf {NP}$$ NP -hardness proof and fixed-parameter algorithm, or $$\mathsf {NP}$$ NP -hardness proof and $$\mathsf {W}[1]$$ W[1] -hardness proof. As corollary, we negatively answer a question by Hamada et al. (Algorithmica 74(1):440–465, 2016) by showing fixed-parameter intractability parameterized by optimal solution size. We also classify all cases of one-sided constraints where only women may be distinguished.

We investigate the odd multiway node (edge) cut problem where the input is a graph with a specified collection of terminal nodes, and the goal is to find a smallest subset of non-terminal nodes (edges) to delete so that the terminal nodes do not have an odd length path between them. In an earlier work, Lokshtanov and Ramanujan showed that both odd multiway node cut and odd multiway edge cut are fixed-parameter tractable (FPT) when parameterized by the size of the solution in undirected graphs. In this work, we focus on directed acyclic graphs (DAGs) and design a fixed-parameter algorithm. Our main contribution is a broadening of the shadow-removal framework to address parity problems in DAGs. We complement our FPT results with tight approximability as well as polyhedral results for two terminals in DAGs. Additionally, we show inapproximability results for odd multiway edge cut in undirected graphs even for two terminals.

Fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet so far those algorithms have been largely restricted to static inputs. In this article, we provide fixed-parameter algorithms and kernelizations for fundamental NP-hard problems with dynamic inputs. We consider a variety of parameterized graph and hitting set problems that are known to have f ( k ) n 1+o(1) time algorithms on inputs of size n , and we consider the question of whether there is a data structure that supports small updates (such as edge/vertex/set/element insertions and deletions) with an update time of g ( k ) n o(1) ; such an update time would be essentially optimal. Update and query times independent of n are particularly desirable. Among many other results, we show that F EEDBACK V ERTEX S ET and k -P ATH admit dynamic algorithms with f ( k )log O(1) update and query times for some function f depending on the solution size k only. We complement our positive results by several conditional and unconditional lower bounds. For example, we show that unlike their undirected counterparts, D IRECTED F EEDBACK V ERTEX S ET and D IRECTED k -P ATH do not admit dynamic algorithms with n o(1) update and query times even for constant solution sizes k ≤ 3 , assuming popular hardness hypotheses. We also show that unconditionally, in the cell probe model, D IRECTED F EEDBACK V ERTEX S ET cannot be solved with update time that is purely a function of k .

The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour of n cities that visits each city c a prescribed number k c of times. Travel costs may be asymmetric, and visiting a city twice in a row may incur a non-zero cost. The MV-TSP problem finds applications in scheduling, geometric approximation, and Hamiltonicity of certain graph families. The fastest known algorithm for MV-TSP is due to Cosmadakis and Papadimitriou (SICOMP, 1984). It runs in time n O(n) + O(n 3 log ∑ c k c ) and requires n ᶿ(n) space. An interesting feature of the Cosmadakis-Papadimitriou algorithm is its logarithmic dependence on the total length ∑ c k c of the tour, allowing the algorithm to handle instances with very long tours. The superexponential dependence on the number of cities in both the time and space complexity, however, renders the algorithm impractical for all but the narrowest range of this parameter. In this article, we improve upon the Cosmadakis-Papadimitriou algorithm, giving an MV-TSP algorithm that runs in time 2 O(n) , i.e., single-exponential in the number of cities, using polynomial space. The space requirement of our algorithm is (essentially) the size of the output, and assuming the Exponential-Time Hypothesis (ETH), the problem cannot be solved in time 2 o(n) . Our algorithm is deterministic, and arguably both simpler and easier to analyze than the original approach of Cosmadakis and Papadimitriou. It involves an optimization over directed spanning trees and a recursive, centroid-based decomposition of trees.

The Directed Feedback Vertex Set (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp’s 21 $$\mathsf {NP}$$ -complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. in 2008 showed its fixed-parameter tractability via a $$4^kk! n^{\mathcal {O}(1)}$$ -time algorithm, where $$k = |S|$$ . Here we show fixed-parameter tractability of two generalizations of DFVS: We also solve the corresponding arc versions of these problems by fixed-parameter algorithms.

The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour of n cities that visits each city c a prescribed number kc of times. Travel costs may be asymmetric, and visiting a city twice in a row may incur a non-zero cost. The MV-TSP problem finds applications in scheduling, geometric approximation, and Hamiltonicity of certain graph families. The fastest known algorithm for MV-TSP is due to Cosmadakis and Papadimitriou (SICOMP, 1984). It runs in time nO(n) + O(n3 log Σc kc) and requires nO(n) space. The interesting feature of the Cosmadakis-Papadimitriou algorithm is its logarithmic dependence on the total length Σc kc of the tour, allowing the algorithm to handle instances with very long tours, beyond what is tractable in the standard TSP setting. However, its superexponential dependence on the number of cities in both its time and space complexity renders the algorithm impractical for all but the narrowest range of this parameter. In this paper we significantly improve on the Cosmadakis-Papadimitriou algorithm, giving an MV-TSP algorithm that runs in time 2O(n), i.e. single-exponential in the number of cities, with polynomial space. The space requirement of our algorithm is (essentially) the size of the output, and assuming the Exponential-time Hypothesis (ETH), the time requirement is optimal. Our algorithm is deterministic, and arguably both simpler and easier to analyse than the original approach of Cosmadakis and Papadimitriou. It involves an optimization over directed spanning trees and a recursive, centroid-based decomposition of trees.

We algorithmize the structural characterization for claw-free graphs by Chudnovsky and Seymour. Building on this result, we show that D ominating S et on claw-free graphs is (i) fixed-parameter tractable and (ii) even possesses a polynomial kernel. To complement these results, we establish that D ominating S et is unlikely to be fixed-parameter tractable on the slightly larger class of graphs that exclude K 1,4 as an induced subgraph ( K 1,4 -free graphs). We show that our algorithmization can also be used to show that the related C onnected D ominating S et problem is fixed-parameter tractable on claw-free graphs. To complement that result, we show that C onnected D ominating S et is unlikely to have a polynomial kernel on claw-free graphs and is unlikely to be fixed-parameter tractable on K 1,4 -free graphs. Combined, our results provide a dichotomy for D ominating S et and C onnected D ominating S et on K 1,ℓ -free graphs and show that the problem is fixed-parameter tractable if and only if ℓ ≤ 3.

We give faster and simpler approximation algorithms for the (1,2)-TSP problem, a well-studied variant of the traveling salesperson problem where all distances between cities are either 1 or 2. Our main results are two approximation algorithms for (1,2)-TSP, one with approximation factor 8/7 and run time O(n^3) and the other having an approximation guarantee of 7/6 and run time O(n^{2.5}). The 8/7-approximation matches the best known approximation factor for (1,2)-TSP, due to Berman and Karpinski (SODA 2006), but considerably improves the previous best run time of O(n^9). Thus, ours is the first improvement for the (1,2)-TSP problem in more than 10 years. The algorithm is based on combining three copies of a minimum-cost cycle cover of the input graph together with a relaxed version of a minimum weight matching, which allows using "half-edges". The resulting multigraph is then edge-colored with four colors so that each color class yields a collection of vertex-disjoint paths. The paths from one color class can then be extended to an 8/7-approximate traveling salesperson tour. Our algorithm, and in particular its analysis, is simpler than the previously best 8/7-approximation. The 7/6-approximation algorithm is similar and even simpler, and has the advantage of not using Hartvigsen's complicated algorithm for computing a minimum-cost triangle-free cycle cover.

In this paper, we study the problem of deciding the winner of reachability switching games. We study zero-, one-, and two-player variants of these games. We show that the zero-player case is NL-hard, the one-player case is NP-complete, and that the two-player case is PSPACE-hard and in EXPTIME. For the zero-player case, we also show P-hardness for a succinctly-represented model that maintains the upper bound of NP n coNP. For the one- and two-player cases, our results hold in both the natural, explicit model and succinctly-represented model. We also study the structure of winning strategies in these games, and in particular we show that exponential memory is required in both the one- and two-player settings.

The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results: We show that an algorithm by Crowston et al. (Algorithmica 72(3):734–757, 2015 ) for (Signed) Max-Cut Above Edwards−Erd ő s Bound can be implemented so as to run in linear time \(8^k\cdot O(m)\) ; this significantly improves the previous analysis with run time \(8^k\cdot O(n^4)\) . We give an asymptotically optimal kernel for (Signed) Max-Cut Above Edwards−Erd ő s Bound with O ( k ) vertices, improving a kernel with \(O(k^3)\) vertices by Crowston et al. (Theor Comput Sci 513:53–64, 2013 ). We improve all known kernels for parameterizations above strongly \(\lambda \) -extendible properties (a generalization of the Max-Cut results) by Crowston et al. (Proceedings of FSTTCS 2013, Leibniz international proceedings in informatics, Guwahati, 2013 ) from \(O(k^3)\) vertices to O ( k ) vertices. Therefore, Max Acyclic Subdigraph parameterized above Poljak–Turzík bound admits a kernel with O ( k ) vertices and can be solved in \(2^{O(k)}\cdot n^{O(1)}\) time; this answers an open question by Crowston et al. (Proceedings of FSTTCS 2012, Leibniz international proceedings in informatics, Hyderabad, 2012 ). All presented kernels can be computed in time O ( km ).

Fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet, so far those algorithms have been largely restricted to static inputs. In this paper we provide fixed-parameter algorithms and kernelizations for fundamental NP-hard problems with dynamic inputs. We consider a variety of parameterized graph and hitting set problems which are known to have f(k)n^{1+o(1)} time algorithms on inputs of size n, and we consider the question of whether there is a data structure that supports small updates (such as edge/vertex/set/element insertions and deletions) with an update time of g(k)n^{o(1)}; such an update time would be essentially optimal. Update and query times independent of n are particularly desirable. Among many other results, we show that Feedback Vertex Set and k-Path admit dynamic algorithms with f(k)log O(1) n update and query times for some function f depending on the solution size k only. We complement our positive results by several conditional and unconditional lower bounds. For example, we show that unlike their undirected counterparts, Directed Feedback Vertex Set and Directed k-Path do not admit dynamic algorithms with n^{o(1) } update and query times even for constant solution sizes k <= 3, assuming popular hardness hypotheses. We also show that unconditionally, in the cell probe model, Directed Feedback Vertex Set cannot be solved with update time that is purely a function of k.

We consider the minimum-weight feedback vertex set problem in tournaments: given a tournament with non-negative vertex weights, remove a minimum-weight set of vertices that intersects all cycles. This problem is $\mathsf{NP}$-hard to solve exactly, and Unique Games-hard to approximate by a factor better than 2. We present the first $7/3$ approximation algorithm for this problem, improving on the previously best known ratio $5/2$ given by Cai et al. [FOCS 1998, SICOMP 2001].

The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results: * We show that an algorithm by Crowston et al. [ICALP 2012] for (Signed) Max-Cut Above Edwards-Erdos Bound can be implemented in such a way that it runs in linear time 8^k · O(m); this significantly improves the previous analysis with run time 8^k · O(n^4). * We give an asymptotically optimal kernel for (Signed) Max-Cut Above Edwards-Erdos Bound with O(k) vertices, improving a kernel with O(k^3) vertices by Crowston et al. [COCOON 2013]. * We improve all known kernels for strongly lambda-extendable properties parameterized above tight lower bound by Crowston et al. [FSTTCS 2013] from O(k^3) vertices to O(k) vertices. * As a consequence, Max Acyclic Subdigraph parameterized above Poljak-Turzik bound admits a kernel with O(k) vertices and can be solved in time 2^{O(k)} * n^{O(1)} ; this answers an open question by Crowston et al. [FSTTCS 2012]. All presented kernels can be computed in time O(km).

We study feedback vertex sets (FVS) in tournaments, which are orientations of complete graphs. As our main result, we show that any tournament on n nodes has at most 1.5949^n minimal FVS. This significantly improves the previously best upper bound of 1.6667^n by Fomin et al. (STOC 2016). Our new upper bound almost matches the best known lower bound of 21^{n/7} approx 1.5448^n, due to Gaspers and Mnich (ESA 2010). Our proof is algorithmic, and shows that all minimal FVS of tournaments can be enumerated in time O(1.5949^n).

We consider the problem to find a set X of vertices (or arcs) with |X| <= k in a given digraph G such that D = G-X is an acyclic digraph. In its generality, this is DIRECTED FEEDBACK VERTEX SET or DIRECTED FEEDBACK ARC SET respectively. The existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made. In this paper, we consider both deletion problems with an additional restriction on D, namely that D must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of these three restrictions the vertex deletion problem remains NP-hard, but we can obtain a kernel with k^{O(1)} vertices on general digraphs G. We also show that, in contrast to the vertex deletion problem, the arc deletion problem with each of the above restrictions can be solved in polynomial time.

We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = \{T_{1},...,T_{t}}, T_i \subseteq V(G), of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that of each set T_{i} at least one pair of terminals is in different connected components of G \ S. This problem generalizes several well-studied graph cut problems, in particular the Multicut problem, which corresponds to the case p = 2. The Multicut problem was recently shown to be fixed-parameter tractable for parameter k [Marx and Razgon, Bousquet et al., STOC 2011]. The question whether this result generalizes to Steiner Multicut motivates the present work. We answer the question that motivated this work, and in fact provide a dichotomy of the parameterized complexity of Steiner Multicut on general graphs. That is, for any combination of k, t, p, and the treewidth tw(G) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable or that the problem is hard (W[1]-hard or even (para-)NP-complete). Among the many results in the paper, we highlight that: - The edge deletion version of Steiner Multicut is fixed-parameter tractable for parameter k+t on general graphs (but has no polynomial kernel, even on trees). - In contrast, both node deletion versions of Steiner Multicut are W[1]-hard for the parameter k+t on general graphs. - All versions of Steiner Multicut are W[1]-hard for the parameter k, even when p=3 and the graph is a tree plus one node. Since we allow k, t, p, and tw(G) to be any constants, our characterization includes a dichotomy for Steiner Multicut on trees (for tw(G) = 1) as well as a polynomial time versus NP-hardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded).

Every triangle-free planar graph on $n$ vertices has an independent set of size at least $(n+1)/3$, and this lower bound is tight. We give an algorithm that, given a triangle-free planar graph $G$ on $n$ vertices and an integer $k\geq0$, decides whether $G$ has an independent set of size at least $(n+k)/3$, in time $2^{O(\sqrt{k})}n$. Thus, the problem is fixed-parameter tractable when parameterized by $k$. Furthermore, as a corollary of the result used to prove the correctness of the algorithm, we show that there exists $\varepsilon>0$ such that every planar graph of girth at least five on $n$ vertices has an independent set of size at least $n/(3-\varepsilon)$. We further give an algorithm that, given a planar graph $G$ of maximum degree 4 on $n$ vertices and an integer $k\geq0$, decides whether $G$ has an independent set of size at least $(n+k)/4$, in time $2^{O(\sqrt{k})}n$.

Poljak and Turzík (Discrete Math. 1986) introduced the notion of lambda-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0 < lambda < 1 and lambda-extendible property Pi, any connected graph G on n vertices and m edges contains a spanning subgraph H in Pi with at least lambda m+ (1-lambda)/2 (n-1) edges. The property of being bipartite is lambda-extendible for lambda=1/2, and thus the Poljak-Turzík bound generalizes the well-known Edwards-Erdos bound for MAXCUT. We define a variant, namely strong lambda-extendibility, to which the Poljak-Turzík bound applies. For a strong lambda-extendible graph property \Pi, we define the parameterized Above Poljak-Turzík problem as follows: Given a connected graph G on n vertices and m edges and an integer parameter k, does there exist a spanning subgraph H of G such that H in Pi and H has at least lambda m+ (1-lambda)/2 (n-1)+k edges? The parameter is k, the surplus over the number of edges guaranteed by the Poljak-Turzík bound. We consider properties Pi for which the Above Poljak-Turzík problem is fixed-parameter tractable (FPT) on graphs which are O(k) vertices away from being a graph in which each block is a clique. We show that for all such properties, Above Poljak-Turzík is FPT for all 0< lambda <1. Our results hold for properties of oriented graphs and graphs with edge labels. Our results generalize the recent result of Crowston et al. (ICALP 2012) on MAXCUT parameterized above the Edwards-Erdos, and yield FPT algorithms for several graph problems parameterized above lower bounds. For instance, we get that the above-guarantee Max q-Colorable Subgraph problem is FPT. Our results also imply that the parameterized above-guarantee Oriented Max Acyclic Digraph problem thus solving an open question of Raman and Saurabh (Theor. Comput. Sci. 2006).

We present a linear-time algorithm that, given a planar graph with $m$ edges and maximum degree $3$, finds an induced matching of size at least $m/9$. This is best possible.