We consider the 1 | | ∑ w j U j problem, the problem of minimizing the weighted number of tardy jobs on a single machine. This problem is one of the most basic and fundamental problems in scheduling theory, with several different applications both in theory and practice. Using a reduction from the Multicolored Clique problem, we prove that 1 | | ∑ w j U j is W[1]-hard with respect to the number p # of different processing times in the input, as well as with respect to the number w # of different weights in the input. This, along with previous work, provides a complete picture for 1 | | ∑ w j U j from the perspective of parameterized complexity, as well as almost tight complexity bounds for the problem under the Exponential Time Hypothesis (ETH).

We provide a linear-time computable problem kernel of linear size for Strongly Stable Roommates parameterized by the feedback edge number of the acceptability graph (which encodes which agents may be matched to each other). • A linear problem kernel for Strongly Stable Matching is provided. • Stability of a matching is sensible to vertex/edge deletion. • Introduction of annotated problem version helps to design reduction rules.

We introduce the problem of adapting a stable matching to forced and forbidden pairs. Given a stable matching M1, a set Q of forced pairs, and a set P of forbidden pairs, we want to find a stable matching that includes all pairs from Q, no pair from P, and is as close as possible to M1. We study this problem in four classic stable matching settings: Stable Roommates (with Ties) and Stable Marriage (with Ties). Our main contribution is a polynomial-time algorithm, based on the theory of rotations, for adapting Stable Roommates matchings to forced pairs. In contrast, we show that the same problem for forbidden pairs is NP-hard. However, our polynomial-time algorithm for forced pairs can be extended to a fixed-parameter tractable algorithm with respect to the number of forbidden pairs. Moreover, we study the setting where preferences contain ties: Some of our algorithmic results can be extended while other problems become intractable.

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_{\#}$.

Focusing on Stable Roommates (SR), we contribute to the toolbox for conducting experiments for stable matching problems. We introduce the polynomial-time computable mutual attraction distance to measure the similarity of SR instances, analyze its properties, and use it to create a map of SR instances. This map visualizes 460 synthetic SR instances (each sampled from one of ten different statistical cultures) as follows: Each instance is a point in the plane, and two points are close on the map if the corresponding SR instances are similar with respect to our mutual attraction distance to each other. Subsequently, we conduct several illustrative experiments and depict their results on the map, illustrating the map’s usefulness as a non-aggregate visualization tool, the diversity of our generated dataset, and the need to use instances sampled from different statistical cultures. Lastly, we extend our approach to the bipartite Stable Marriage problem.

We study the computational complexity of several polynomial-time-solvable graph problems parameterized by vertex integrity, a measure of a graph’s vulnerability to vertex removal in terms of connectivity. Vertex integrity is the smallest number ι such that there is a set S of ι' ≤ ι vertices such that every connected component of G-S contains at most ι-ι' vertices. It is known that the vertex integrity lies between the well-studied parameters vertex cover number and tree-depth. Our work follows similar studies for vertex cover number [Alon and Yuster, ESA 2007] and tree-depth [Iwata, Ogasawara, and Ohsaka, STACS 2018]. Alon and Yuster designed algorithms for graphs with small vertex cover number using fast matrix multiplications. We demonstrate that fast matrix multiplication can also be effectively used when parameterizing by vertex integrity ι by developing efficient algorithms for problems including an O(ι^{ω-1}n)-time algorithm for Maximum Matching and an O(ι^{(ω-1)/2}n²) ⊆ O(ι^{0.687} n²)-time algorithm for All-Pairs Shortest Paths. These algorithms can be faster than previous algorithms parameterized by tree-depth, for which fast matrix multiplication is not known to be effective.

We provide a general framework to exclude parameterized running times of the form $O(\ell^β+ n^γ)$ for problems that have polynomial running time lower bounds under hypotheses from fine-grained complexity. Our framework is based on cross-compositions from parameterized complexity. We (conditionally) exclude running times of the form $O(\ell^{γ/{(γ-1)} - ε} + n^γ)$ for any $1<γ<2$ and $ε>0$ for the following problems: - Longest Common Subsequence: Given two length-$n$ strings and $\ell\in\mathbb{N}$, is there a common subsequence of length $\ell$? - Discrete Fréchet Distance: Given two lists of $n$ points each and $k\in \mathbb{N}$, is the Fréchet distance of the lists at most $k$? Here $\ell$ is the maximum number of points which one list is ahead of the other list in an optimum traversal. Moreover, we exclude running times $O(\ell^{{2γ}/{(γ-1)}-ε} + n^γ)$ for any $1<γ<3$ and $ε>0$ for: - Negative Triangle: Given an edge-weighted graph with $n$ vertices, is there a triangle whose sum of edge-weights is negative? Here $\ell$ is the order of a maximum connected component. - Triangle Collection: Given a vertex-colored graph with $n$ vertices, is there for each triple of colors a triangle whose vertices have these three colors? Here $\ell$ is the order of a maximum connected component. - 2nd Shortest Path: Given an $n$-vertex edge-weighted directed graph, two vertices $s$ and $t$, and $k \in \mathbb{N}$, has the second longest $s$-$t$-path length at most $k$? Here $\ell$ is the directed feedback vertex set. Except for 2nd Shortest Path all these running time bounds are tight, that is, algorithms with running time $O(\ell^{γ/{(γ-1)}} + n^γ)$ for any $1 < γ< 2$ and $O(\ell^{{2γ}/{(γ-1)}} + n^γ)$ for any $1 < γ< 3$, respectively, are known.

Following up on purely theoretical work, we contribute further theoretical insights into adapting stable two-sided matchings to change. Moreover, we perform extensive empirical studies hinting at numerous practically useful properties. Our theoretical extensions include the study of new problems (that is, incremental variants of Almost Stable Marriage and Hospital Residents), focusing on their (parameterized) computational complexity and the equivalence of various change types (thus simplifying algorithmic and complexity-theoretic studies for various natural change scenarios). Our experimental findings reveal, for instance, that allowing the new matching to be blocked by a few pairs significantly decreases the difference between the old and the new matching.

We study the Length-Bounded Cut problem for special graph classes and from a parameterized complexity viewpoint. Here, we are given a graph G, two vertices s and t, and positive integers β and λ. The task is to find a set F of at most β edges such that each s-t-path of length at most λ in G contains some edge in F. Bazgan et al. [20] conjectured that Length-Bounded Cut admits a polynomial-time algorithm if the input graph is a proper interval graph. We confirm this conjecture by providing a dynamic-programming-based polynomial-time algorithm. Moreover, we strengthen the W[1]-hardness result of Dvořák and Knop [15] for Length-Bounded Cut parameterized by pathwidth by showing W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that Length-Bounded Cut is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms.

We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalization lies in simultaneously considering several instances of the problem at once. In particular, we have n clients over a period of m days, where each client has a single job with its own processing time and deadline per day. Our goal is to provide a schedule for each of the m days, so that each client is guaranteed to have their job meet its deadline in at least k

In the presented paper, we study the Length-Bounded Cut problem for special graph classes as well as from a parameterized-complexity viewpoint. Here, we are given a graph G, two vertices s and t, and positive integers β and λ. The task is to find a set F of edges of size at most β such that every s-t-path of length at most λ in G contains some edge in F. Bazgan et al. [Networks, 2019] conjectured that Length-Bounded Cut admits a polynomial-time algorithm if the input graph G is a proper interval graph. We confirm this conjecture by providing a dynamic-programming based polynomial-time algorithm. Moreover, we strengthen the W[1]-hardness result of Dvořák and Knop [Algorithmica, 2018] for Length-Bounded Cut parameterized by pathwidth. Our reduction is shorter, and the target of the reduction has stronger structural properties. Consequently, we give W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that Length-Bounded Cut is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms.

We initiate the study of external manipulations in Stable Marriage by considering several manipulative actions as well as several manipulation goals. For instance, one goal is to make sure that a given pair of agents is matched in a stable solution, and this may be achieved by the manipulative action of reordering some agents' preference lists. We present a comprehensive study of the computational complexity of all problems arising in this way. We find several polynomial-time solvable cases as well as NP-hard ones. For the NP-hard cases, focusing on the natural parameter "budget" (that is, the number of manipulative actions one is allowed to perform), we also conduct a parameterized complexity analysis and encounter mostly parameterized hardness results.

We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the side of fixed-parameter tractability. Other than for its famous sister problem Stable Marriage which focuses on a bipartite scenario, Stable Roommates with Incomplete Lists allows for arbitrary acceptability graphs whose edges specify the possible matchings of each two agents (agents are represented by graph vertices). Herein, incomplete lists and ties reflect the fact that in realistic application scenarios the agents cannot bring all other agents into a linear order. Among our main contributions is to show that it is W[1]-hard to compute a maximum-cardinality stable matching for acceptability graphs of bounded treedepth, bounded tree-cut width, and bounded feedback vertex number (these are each time the respective parameters). However, if we "only" ask for perfect stable matchings or the mere existence of a stable matching, then we obtain fixed-parameter tractability with respect to tree-cut width but not with respect to treedepth. On the positive side, we also provide fixed-parameter tractability results for the parameter feedback edge set number.

We present a $\frac{10}{7}$-approximation algorithm for the minimum 2-vertex-connected spanning subgraph problem. Similarly to the work of Cheriyan, Sebö, and Szigeti for 2-edge-connected spanning subgraphs, our algorithm is based on computing a carefully designed ear-decomposition.