In this paper, we study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices. In particular, we study self-deleting graphs, introduced by Carmesin et al. [Sarah Carmesin et al., 2023], which consist of a graph G = (V, E) and a function f: V → 2^E, where f(v) is the set of edges that will be deleted after visiting the vertex v. In the (Shortest) Self-Deleting s-t-path problem we are given a self-deleting graph and its vertices s and t, and we are asked to find a (shortest) path from s to t, such that it does not traverse an edge in f(v) after visiting v for any vertex v. We prove that Self-Deleting s-t-path is NP-hard even if the given graph is outerplanar, bipartite, has maximum degree 3, bandwidth 2 and |f(v)| ≤ 1 for each vertex v. We show that Shortest Self-Deleting s-t-path is W[1]-complete parameterized by the length of the sought path and that Self-Deleting s-t-path is W[1]-complete parameterized by the vertex cover number, feedback vertex set number and treedepth. We also show that the problem becomes FPT when we parameterize by the maximum size of f(v) and several structural parameters. Lastly, we show that the problem does not admit a polynomial kernel even for parameterization by the vertex cover number and the maximum size of f(v) combined already on 2-outerplanar graphs.

Abstract We introduce and discuss the problem: given a directed graph with edge capacities $$\textit{cap} $$ cap and a retention ratio $$\alpha \in (0,1)$$ α ∈ ( 0 , 1 ) , find the smallest subgraph that, for each pair of vertices ( u , v ), preserves at least a fraction $$\alpha $$ α of a maximum u - v -flow’s value. This problem originates from the practical setting of reducing the power consumption in a computer network: it models turning off as many links as possible, while retaining the ability to transmit at least $$\alpha $$ α times the traffic compared to the original network. First we prove that is NP-hard already on a restricted set of directed acyclic graphs (DAGs) with unit edge capacities. Our reduction also shows that a closely related problem (which only considers the arguably most complicated core of the problem in the objective function) is NP-hard to approximate within a sublogarithmic factor already on DAGs. In terms of positive results, we present two algorithms that solve optimally on directed series-parallel graphs (DSPs): a simple linear-time algorithm for the special case of unit edge capacities and a cubic-time dynamic programming algorithm for the general case of non-uniform edge capacities. Further, we introduce the family of laminar series-parallel graphs (LSPs), a generalization of DSPs that also includes cyclic and very dense graphs. Their properties allow us to solve on LSPs by employing our DSP-algorithms as subroutines. In addition, we give a separate quadratic-time algorithm for on LSPs with unit edge capacities that also yields straightforward quadratic time algorithms for several related problems such as and on LSPs.

Green Traffic Engineering encompasses network design and traffic routing strategies that aim at reducing the power consumption of a backbone network. We argue that turning off linecards is the most effective practically feasible approach to reach this goal. Thus, we investigate the problem of minimizing the number of active line cards in a network while simultaneously allowing a multi-commodity flow being routed and keeping the maximum link utilization below a certain threshold. In addition to proving this problem to be NP-hard, we present an optimal ILP-based algorithm as well as a heuristic based on 2-Segment Routing. Lastly, we evaluate both approaches on real-world networks obtained from the Repetita Framework and a globally operating Internet Service Provider. The results of this evaluation indicate that our heuristic is not only close to optimal but significantly faster than the optimal algorithm, making it viable in practice.