We study the computational complexity of determining structural properties of edge-periodic temporal graphs (EPGs). EPGs are time-varying graphs that compactly represent periodic behavior of components of a dynamic network, for example, train schedules on a rail network. In EPGs, for each edge e of the graph, a binary string τ ( e ) determines in which time steps the edge is present, namely e is present in time step t if and only if τ ( e ) contains a 1 at position t mod | τ ( e ) | . Due to this periodicity, EPGs serve as very compact representations of complex periodic systems and can even be exponentially smaller than classic temporal graphs representing one period of the same system, as the latter contain the whole sequence of graphs explicitly. In this paper, we study the computational complexity of fundamental questions of the concept of EPGs such as : Is there a time step or a sliding window of size Δ in which the graph (1) is minor-free; (2) contains a minor; (3) is induced subgraph-free; (4) contains an induced subgraph; with respect to a given minor or subgraph. We give a detailed parameterized analysis for multiple combinations of parameters for the problems stated above including several algorithms. Additionally, we study the parameterized complexity of the short traversal problem in EPGs. In this problem, one asks whether there exists a time step t such that one can reach a vertex b from a vertex a at time step at most t + k for given k .

32:1

In the NP-hard Max c-Cut problem, one is given an undirected edge-weighted graph G and wants to color the vertices of G with c colors such that the total weight of edges with distinctly colored endpoints is maximal. The case with c=2 is the famous Max Cut problem. To deal with the NP-hardness of this problem, we study parameterized local search algorithms. More precisely, we study LS-Max c-Cut where we are additionally given a vertex coloring f and an integer k and the task is to find a better coloring f' that differs from f in at most k entries, if such a coloring exists; otherwise, f is k-optimal. We show that LS-Max c-Cut presumably cannot be solved in g(k) · nᴼ⁽¹⁾ time even on bipartite graphs, for all c ≥ 2. We then show an algorithm for LS-Max c-Cut with running time O((3eΔ)ᵏ · c · k³ · Δ · n), where Δ is the maximum degree of the input graph. Finally, we evaluate the practical performance of this algorithm in a hill-climbing approach as a post-processing for state-of-the-art heuristics for Max c-Cut. We show that using parameterized local search, the results of this heuristic can be further improved on a set of standard benchmark instances.

Automated storage and retrieval systems (ASRS) are important in distribution centers and warehouses. To decrease cost or CO2emissions it is natural to optimize various aspects of an ASRS. In this work, we provide a concept for a two-phase optimization combining two important optimization tasks in ASRS: Given multiple rearrangement jobs, we first sequence these jobs to minimize the total travelling distance of the cranes. We continue the optimization by computing optimal trajectories for the sequence to guarantee energy efficient driving of the cranes. We describe our algorithms for a complex ASRS architecture with two cranes on parallel rails in one aisle. Additionally, we describe how to use our results for parallelization of crane movements in the considered warehouse architecture.

We consider the problem of scheduling production jobs on a single machine with sequence dependent family setup times and individual job deadlines. Given a set of jobs, the goal is to minimize the total time to process all jobs while every job meets its deadline. We study algorithms that compute an exact solution to the problem. Motivated by one example use case, we exploit a natural structural observation that occurs in many production settings: the number of product configurations may be significantly smaller than the total number of jobs. We identify an algorithm that is efficient in this setting in terms of performance. We experimentally evaluate its running time and compare it with two other natural approaches of exact job scheduling.

We study the problem of learning the structure of an optimal Bayesian network when additional constraints are posed on the network or on its moralized graph. More precisely, we consider the constraint that the network or its moralized graph are close, in terms of vertex or edge deletions, to a sparse graph class Π. For example, we show that learning an optimal network whose moralized graph has vertex deletion distance at most k from a graph with maximum degree 1 can be computed in polynomial time when k is constant. This extends previous work that gave an algorithm with such a running time for the vertex deletion distance to edgeless graphs. We then show that further extensions or improvements are presumably impossible. For example, we show that learning optimal networks where the network or its moralized graph have maximum degree 2 or connected components of size at most c, c ≥ 3, is NP-hard. Finally, we show that learning an optimal network with at most k edges in the moralized graph presumably has no f(k) · |I|O(1)-time algorithm and that, in contrast, an optimal network with at most k arcs can be computed in 2O(k) · |I|O(1) time where |I| is the total input size.

Abstract In the NP-hard Colored (s,t)-Cut problem, the input is a graph G = (V,E) together with an edge-coloring ℓ : E → C, two vertices s and t, and a number k. The question is whether there is a set $S\subseteq C$ S ⊆ C of at most k colors such that deleting every edge with a color from S destroys all paths between s and t in G. We continue the study of the parameterized complexity of Colored (s,t)-Cut. First, we consider parameters related to the structure of G. For example, we study parameterization by the number ξi of edge deletions that are needed to transform G into a graph with maximum degree i. We show that Colored (s,t)-Cut is W[2]-hard when parameterized by ξ3, but fixed-parameter tractable when parameterized by ξ2. Second, we consider parameters related to the coloring ℓ. We show fixed-parameter tractability for three parameters that are potentially smaller than the total number of colors |C| and provide a linear-size problem kernel for a parameter related to the number of edges with rare edge colors.

In Bayesian Network Structure Learning (BNSL), we are given a variable set and parent scores for each variable and aim to compute a DAG, called Bayesian network, that maximizes the sum of parent scores, possibly under some structural constraints. Even very restricted special cases of BNSL are computationally hard, and, thus, in practice heuristics such as local search are used. In a typical local search algorithm, we are given some BNSL solution and ask whether there is a better solution within some pre-defined neighborhood of the solution. We study ordering-based local search, where a solution is described via a topological ordering of the variables. We show that given such a topological ordering, we can compute an optimal DAG whose ordering is within inversion distance r in subexponential FPT time; the parameter r allows to balance between solution quality and running time of the local search algorithm. This running time bound can be achieved for BNSL without any structural constraints and for all structural constraints that can be expressed via a sum of weights that are associated with each parent set. We show that for other modification operations on the variable orderings, algorithms with an FPT time for r are unlikely. We also outline the limits of ordering-based local search by showing that it cannot be used for common structural constraints on the moralized graph of the network.

A Bayesian network is a directed acyclic graph that represents statistical dependencies between variables of a joint probability distribution. A fundamental task in data science is to learn a Bayesian network from observed data. Polytree Learning is the problem of learning an optimal Bayesian network that fulfills the additional property that its underlying undirected graph is a forest. In this work, we revisit the complexity of Polytree Learning. We show that Polytree Learning can be solved in single-exponential FPT time for the number of variables. Moreover, we consider the influence of d, the number of variables that might receive a nonempty parent set in the final DAG on the complexity of Polytree Learning. We show that Polytree Learning is presumably not fixed-parameter tractable for d, unlike Bayesian network learning which is fixed-parameter tractable for d. Finally, we show that if d and the maximum parent set size are bounded, then we can obtain efficient algorithms.

We study the problem of learning the structure of an optimal Bayesian network when additional structural constraints are posed on the network or on its moralized graph. More precisely, we consider the constraint that the moralized graph can be transformed to a graph from a sparse graph class Π by at most k vertex deletions. We show that for Π being the graphs with maximum degree 1, an optimal network can be computed in polynomial time when k is constant, extending previous work that gave an algorithm with such a running time for Π being the class of edgeless graphs [Korhonen & Parviainen, NIPS 2015]. We then show that further extensions or improvements are presumably impossible. For example, we show that when Π is the set of graphs in which each component has size at most three, then learning an optimal network is NP-hard even if k=0. Finally, we show that learning an optimal network with at most k edges in the moralized graph presumably is not fixed-parameter tractable with respect to k and that, in contrast, computing an optimal network with at most k arcs can be computed is fixed-parameter tractable in k.