Abstract We settle the parameterized complexities of several variants of independent set reconfiguration and dominating set reconfiguration, parameterized by the number of tokens. We show that both problems are XL-complete when there is no limit on the number of moves, XNL-complete when a maximum length $$\ell $$ ℓ for the sequence is given in binary in the input, and XNLP-complete when $$\ell $$ ℓ is given in unary. The problems were known to be $$\textrm{W}[1]$$ W [ 1 ] - and $$\textrm{W}[2]$$ W [ 2 ] -hard respectively when $$\ell $$ ℓ is also a parameter. We complete the picture by showing membership in those classes. Moreover, we show that for all the variants that we consider, token sliding and token jumping are equivalent under pl-reductions. We introduce partitioned variants of token jumping and token sliding, and give pl-reductions between the four variants that have precise control over the number of tokens and the length of the reconfiguration sequence.

In a classical scheduling problem, we are given a set of n jobs of unit length with precedence constraints, and the goal is to find a schedule of these jobs on m identical machines that minimizes the makespan. In standard 3-field notation, it is denoted as Pm|prec,pj = 1 |Cmax.

In the Steiner Tree problem we are given an undirected edge-weighted graph as input, along with a set K of vertices called terminals. The task is to output a minimum-weight connected subgraph that spans all the terminals. The famous Dreyfus-Wagner algorithm running in 3^{|K|}poly(n) time shows that the problem is fixed-parameter tractable parameterized by the number of terminals. We present fixed-parameter tractable algorithms for Steiner Tree using structurally smaller parameterizations. Our first result concerns the parameterization by a multiway cut S of the terminals, which is a vertex set S (possibly containing terminals) such that each connected component of G-S contains at most one terminal. We show that Steiner Tree can be solved in 2^{𝒪(|S|log|S|)}poly(n) time and polynomial space, where S is a minimum multiway cut for K. The algorithm is based on the insight that, after guessing how an optimal Steiner tree interacts with a multiway cut S, computing a minimum-cost solution of this type can be formulated as minimum-cost bipartite matching. Our second result concerns a new hybrid parameterization called K-free treewidth that simultaneously refines the number of terminals |K| and the treewidth of the input graph. By utilizing recent work on ℋ-Treewidth in order to find a corresponding decomposition of the graph, we give an algorithm that solves Steiner Tree in time 2^{𝒪(k)} poly(n), where k denotes the K-free treewidth of the input graph. To obtain this running time, we show how the rank-based approach for solving Steiner Tree parameterized by treewidth can be extended to work in the setting of K-free treewidth, by exploiting existing algorithms parameterized by |K| to compute the table entries of leaf bags of a tree K-free decomposition.

Let XNLP be the class of parameterized problems such that an instance of size n with parameter k can be solved nondeterministically in time f(k)nO(1) and space f(k)log⁡(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as List Coloring and Precoloring Extension with pathwidth as parameter, Scheduling of Jobs with Precedence Constraints, with both number of machines and partial order width as parameter, Bandwidth and variants of Weighted CNF-Satisfiability. In particular, this implies that all these problems are W[t]-hard for all t.

Abstract. In the Bin Packing problem one is given [Formula: see text] items with weights [Formula: see text] and [Formula: see text] bins with capacities [Formula: see text]. The goal is to partition the items into sets [Formula: see text] such that [Formula: see text] for every bin [Formula: see text], where [Formula: see text] denotes [Formula: see text]. Björklund, Husfeldt, and Koivisto [ SIAM J. Comput., 39 (2009), pp. 546–563] presented an [Formula: see text] time algorithm for Bin Packing (the [Formula: see text] notation omits factors polynomial in the input size). In this paper, we show that for every [Formula: see text] there exists a constant [Formula: see text] such that an instance of Bin Packing with [Formula: see text] bins can be solved in [Formula: see text] randomized time. Before our work, such improved algorithms were not known even for [Formula: see text]. A key step in our approach is the following new result in Littlewood–Offord theory on the additive combinatorics of subset sums: For every [Formula: see text] there exists an [Formula: see text] such that if [Formula: see text] for some [Formula: see text], then [Formula: see text].

Abstract. For many algorithmic problems on graphs of treewidth [Formula: see text], a standard dynamic programming approach gives algorithms with time and space complexity [Formula: see text]. It turns out that when one considers the more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the space complexity to polynomial, while retaining time complexity of the form [Formula: see text], where [Formula: see text] is the treedepth. This transfer of methodology is, however, far from automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with time and space complexity [Formula: see text] on graphs of treewidth [Formula: see text], but it is not clear how to convert them into time-efficient polynomial space algorithms for graphs of low treedepth. Cygan et al. [ ACM Trans. Algorithms, 18 (2022), 17] introduced the Cut&Count technique and showed that a certain class of problems with connectivity constraints can be solved in time and space complexity [Formula: see text]. Recently, Hegerfeld and Kratsch (STACS’20) showed that, for some of those problems, the Cut&Count technique can be also applied in the setting of treedepth, and it gives algorithms with running time [Formula: see text] and polynomial space usage. However, several important problems eluded such a treatment, with the most prominent examples being Hamiltonian Cycle and Longest Path. In this paper, we clarify the situation by showing that Hamiltonian cycle, Hamiltonian Path, Long Cycle, Long Path, and Min Cycle Cover all admit [Formula: see text]-time and polynomial space algorithms on graphs of treedepth [Formula: see text]. The algorithms are randomized Monte Carlo with only false negatives.

The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87] provides a self-reduction scheme that allows one to assume that a given instance of a problem has a unique solution, provided a solution exists at all. Since its introduction, much effort has been dedicated towards derandomization of the Isolation Lemma for specific classes of problems. So far, the focus was mainly on problems solvable in polynomial time. In this paper, we study a setting that is more typical for $\mathsf{NP}$-complete problems, and obtain partial derandomizations in the form of significantly decreasing the number of required random bits. In particular, motivated by the advances in parameterized algorithms, we focus on problems on decomposable graphs. For example, for the problem of detecting a Hamiltonian cycle, we build upon the rank-based approach from [Bodlaender et al., Inf. Comput.'15] and design isolation schemes that use - $O(t\log n + \log^2{n})$ random bits on graphs of treewidth at most $t$; - $O(\sqrt{n})$ random bits on planar or $H$-minor free graphs; and - $O(n)$-random bits on general graphs. In all these schemes, the weights are bounded exponentially in the number of random bits used. As a corollary, for every fixed $H$ we obtain an algorithm for detecting a Hamiltonian cycle in an $H$-minor-free graph that runs in deterministic time $2^{O(\sqrt{n})}$ and uses polynomial space; this is the first algorithm to achieve such complexity guarantees. For problems of more local nature, such as finding an independent set of maximum size, we obtain isolation schemes on graphs of treedepth at most $d$ that use $O(d)$ random bits and assign polynomially-bounded weights. We also complement our findings with several unconditional and conditional lower bounds, which show that many of the results cannot be significantly improved.

Abstract We study a natural variant of scheduling that we call partial scheduling: in this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by k for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type $$f(k)n^{{\mathcal {O}}(1)}$$ f ( k ) n O ( 1 ) or $$n^{{\mathcal {O}}(f(k))}$$ n O ( f ( k ) ) exist for a function f that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in $${\mathsf {P}}$$ P , $${{\mathsf {N}}}{{\mathsf {P}}}$$ N P -complete and fixed-parameter tractable by k, or $${\mathsf {W}}[1]$$ W [ 1 ] -hard parameterized by k. Second, for many interesting cases we further investigate the runtime on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an $${\mathcal {O}}(8^kk(|V|+|E|))$$ O ( 8 k k ( | V | + | E | ) ) time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where $$G=(V,E)$$ G = ( V , E ) is the graph with precedence constraints.

Let XNLP be the class of parameterized prob-lems such that an instance of size$n$with parameter$k$can be solved nondeterministically in time$f$($k$) nO(1)and space f (k) log(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as List Coloringand Precoloring Extensionwith pathwidth as parameter, Scheduling Of Jobs With Precedence Constraints, with both number of machines and partial order width as parameter, Bandwidthand variants of Weighted Cnf-satisfiability and reconfiguration problems. In particular, this implies that all these problems are W[$t$]-hard for all t. This also answers a long standing question on the parameterized complexity of the Bandwidth problem.

In the Bin Packing problem one is given n items with weights w1, …, wn and m bins with capacities c1, …, cm. The goal is to find a partition of the items into sets S1, …, Sm such that w(Sj) ≤ cj for every bin j, where w(X) denotes Σi∊xwi. Björklund, Husfeldt and Koivisto (SICOMP 2009) presented an time algorithm for Bin Packing. In this paper, we show that for every m ∊ ℕ there exists a constant σm > 0 such that an instance of Bin Packing with m bins can be solved in randomized time. Before our work, such improved algorithms were not known even for m equals 4. A key step in our approach is the following new result in Littlewood-Offord theory on the additive combinatorics of subset sums: For every δ > 0 there exists an ∊ > 0 such that if |{X ⊆ {1, …, n} : w(X) = v}| ≥ 2(1–∊)n for some v then |{w(X) : X ⊆ {1, …, n}}| ≤ 2δn.