Search

We introduce the algorithmic problem of finding a locally rainbow path of length $\ell$ connecting two distinguished vertices $s$ and $t$ in a vertex-colored directed graph. Herein, a path is locally rainbow if between any two visits of equally colored vertices, the path traverses consecutively at least $r$ differently colored vertices. This problem generalizes the well-known problem of finding a rainbow path. It finds natural applications whenever there are different types of resources that must be protected from overuse, such as crop sequence optimization or production process scheduling. We show that the problem is computationally intractable even if $r=2$ or if one looks for a locally rainbow among the shortest paths. On the positive side, if one looks for a path that takes only a short detour (i.e., it is slightly longer than the shortest path) and if $r$ is small, the problem can be solved efficiently. Indeed, the running time of the respective algorithm is near-optimal unless the ETH fails., Comment: Accepted at AAAI 2024

A graph with vertex set $\{1,\ldots,n\}$ is terrain-like if, for any edge pair $\{a,c\},\{b,d\}$ with $a

A temporal graph is a graph whose edges appear only at certain points in time. Recently, the second and the last three authors proposed a natural temporal analog of the Erd\H{o}s-R\'enyi random graph model. The proposed model is obtained by randomly permuting the edges of an Erd\H{o}s-R\'enyi random graph and interpreting this permutation as an ordering of presence times. It was shown that the connectivity threshold in the Erd\H{o}s-R\'enyi model fans out into multiple phase transitions for several distinct notions of reachability in the temporal setting. In the present paper, we identify a sharp threshold for the emergence of a giant temporally connected component. We show that at $p = \log n/n$ the size of the largest temporally connected component increases from $o(n)$ to~$n-o(n)$. This threshold holds for both open and closed connected components, i.e. components that allow, respectively forbid, their connecting paths to use external nodes.

Most transportation networks are inherently temporal: Connections (e.g. flights, train runs) are only available at certain, scheduled times. When transporting passengers or commodities, this fact must be considered for the the planning of itineraries. This has already led to several well-studied algorithmic problems on temporal graphs. The difficulty of the described task is increased by the fact that connections are often unreliable -- in particular, many modes of transportation suffer from occasional delays. If these delays cause subsequent connections to be missed, the consequences can be severe. Thus, it is a vital problem to design itineraries that are robust to (small) delays. We initiate the study of this problem from a parameterized complexity perspective by proving its NP-completeness as well as several hardness and tractability results for natural parameterizations.

Consider planning a trip in a train network. In contrast to, say, a road network, the edges are temporal, i.e., they are only available at certain times. Another important difficulty is that trains, unfortunately, sometimes get delayed. This is especially bad if it causes one to miss subsequent trains. The best way to prepare against this is to have a connection that is robust to some number of (small) delays. An important factor in determining the robustness of a connection is how far in advance delays are announced. We give polynomial-time algorithms for the two extreme cases: delays known before departure and delays occurring without prior warning (the latter leading to a two-player game scenario). Interestingly, in the latter case, we show that the problem becomes PSPACE-complete if the itinerary is demanded to be a path.

While there have been numerous reports of long-range polariton transport at room-temperature in organic cavities, the spatio-temporal evolution of the propagation is scarcely reported, particularly in the initial coherent sub-ps regime, where photon and exciton wavefunctions are inextricably mixed. Hence the detailed process of coherent organic exciton-polariton transport and in particular the role of dark states has remained poorly understood. Here, we use femtosecond transient absorption microscopy to directly image coherent polariton motion in microcavities of varying quality factor. We find the transport to be well-described by a model of band-like propagation of an initially Gaussian distribution of exciton-polaritons in real space. The velocity of the polaritons reaches values of ~0.65x10^6 m s-1, substantially lower than expected from the polariton dispersion. Further, we find that the velocity is proportional to the quality factor of the microcavity. We suggest this unexpected link between the quality-factor and polariton velocity and slow coherent transport to be a result of varying admixing between delocalised dark and polariton states.

Strong light-matter coupling to form exciton- and vibropolaritons is increasingly touted as a powerful tool to alter the fundamental properties of organic materials. It is proposed that these states and their facile tunability can be used to rewrite molecular potential energy landscapes and redirect photophysical pathways, with applications from catalysis to electronic devices. Crucial to their photophysical properties is the exchange of energy between coherent, bright polaritons and incoherent dark states. One of the most potent tools to explore this interplay is transient absorption/reflectance spectroscopy. Previous studies have revealed unexpectedly long lifetimes of the coherent polariton states, for which there is no theoretical explanation. Applying these transient methods to a series of strong-coupled organic microcavities, we recover similar long-lived spectral effects. Based on transfer-matrix modelling of the transient experiment, we find that virtually the entire photoresponse results from photoexcitation effects other than the generation of polariton states. Our results suggest that the complex optical properties of polaritonic systems make them especially prone to misleading optical signatures, and that more challenging high-time-resolution measurements on high-quality microcavities are necessary to uniquely distinguish the coherent polariton dynamics.

Proximity graphs have been studied for several decades, motivated by applications in computational geometry, geography, data mining, and many other fields. However, the computational complexity of classic graph problems on proximity graphs mostly remained open. We now study 3-Colorability, Dominating Set, Feedback Vertex Set, Hamiltonian Cycle, and Independent Set on the proximity graph classes relative neighborhood graphs, Gabriel graphs, and relatively closest graphs. We prove that all of the problems remain NP-hard on these graphs, except for 3-Colorability and Hamiltonian Cycle on relatively closest graphs, where the former is trivial and the latter is left open. Moreover, for every NP-hard case we additionally show that no $2^{o(n^{1/4})}$-time algorithm exists unless the ETH fails, where n denotes the number of vertices.

Removing all connections between two vertices s and z in a graph by removing a minimum number of vertices is a fundamental problem in algorithmic graph theory. This (s,z)-separation problem is well-known to be polynomial solvable and serves as an important primitive in many applications related to network connectivity. We study the NP-hard temporal (s,z)-separation problem on temporal graphs, which are graphs with fixed vertex sets but edge sets that change over discrete time steps. We tackle this problem by restricting the layers (i.e., graphs characterized by edges that are present at a certain point in time) to specific graph classes. We restrict the layers of the temporal graphs to be either all split graphs or all permutation graphs (both being perfect graph classes) and provide both intractability and tractability results. In particular, we show that in general the problem remains NP-hard both on temporal split and temporal permutation graphs, but we also spot promising islands of fixed-parameter tractability particularly based on parameterizations that measure the amount of "change over time".

To address the dynamic nature of real-world networks, we generalize competitive diffusion games and Voronoi games from static to temporal graphs, where edges may appear or disappear over time. This establishes a new direction of studies in the area of graph games, motivated by applications such as influence spreading. As a first step, we investigate the existence of Nash equilibria in 2-player competitive diffusion and Voronoi games on different temporal graph classes. Even when restricting our studies to temporal trees and cycles, this turns out to be a challenging undertaking, revealing significant differences between the two games in the temporal setting. Notably, both games are equivalent on static trees and cycles. Our two main technical results are (algorithmic) proofs for the existence of Nash equilibria in 2-player competitive diffusion and temporal Voronoi games when the edges are restricted not to disappear over time., Comment: Accepted to IJCAI 2021

The world is rarely static -- many problems need not only be solved once but repeatedly, under changing conditions. This setting is addressed by the "multistage" view on computational problems. We study the "diverse multistage" variant, where consecutive solutions of large variety are preferable to similar ones, e.g. for reasons of fairness or wear minimization. While some aspects of this model have been tackled before, we introduce a framework allowing us to prove that a number of diverse multistage problems are fixed-parameter tractable by diversity, namely Perfect Matching, s-t Path, Matroid Independent Set, and Plurality Voting. This is achieved by first solving special, colored variants of these problems, which might also be of independent interest.

We study spreading processes in temporal graphs, i. e., graphs whose connections change over time. These processes naturally model real-world phenomena such as infectious diseases or information flows. More precisely, we investigate how such a spreading process, emerging from a given set of sources, can be contained to a small part of the graph. To this end we consider two ways of modifying the graph, which are (1) deleting connections and (2) delaying connections. We show a close relationship between the two associated problems and give a polynomial time algorithm when the graph has tree structure. For the general version, we consider parameterization by the number of vertices to which the spread is contained. Surprisingly, we prove W[1]-hardness for the deletion variant but fixed-parameter tractability for the delaying variant.

In a temporal network with discrete time-labels on its edges, entities and information can only "flow" along sequences of edges whose time-labels are non-decreasing (resp. increasing), i.e. along temporal (resp. strict temporal) paths. Nevertheless, in the model for temporal networks of [Kempe et al., JCSS, 2002], the individual time-labeled edges remain undirected: an edge $e=\{u,v\}$ with time-label $t$ specifies that "$u$ communicates with $v$ at time $t$". This is a symmetric relation between $u$ and $v$, and it can be interpreted that the information can flow in either direction. In this paper we make a first attempt to understand how the direction of information flow on one edge can impact the direction of information flow on other edges. More specifically, we introduce the notion of a temporal transitive orientation and we systematically investigate its algorithmic behavior in various situations. An orientation of a temporal graph is called temporally transitive if, whenever $u$ has a directed edge towards $v$ with time-label $t_1$ and $v$ has a directed edge towards $w$ with time-label $t_2\geq t_1$, then $u$ also has a directed edge towards $w$ with some time-label $t_3\geq t_2$. If we just demand that this implication holds whenever $t_2 > t_1$, the orientation is called strictly temporally transitive. Our main result is a conceptually simple, yet technically quite involved, polynomial-time algorithm for recognizing whether a given temporal graph $\mathcal{G}$ is transitively orientable. In wide contrast we prove that, surprisingly, it is NP-hard to recognize whether $\mathcal{G}$ is strictly transitively orientable. Additionally we introduce and investigate further related problems to temporal transitivity, notably among them the temporal transitive completion problem, for which we prove both algorithmic and hardness results.

A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this paper, we consider a simple model of random temporal graph, obtained from an Erd\H{o}s-R\'enyi random graph $G~G_{n,p}$ by considering a random permutation $\pi$ of the edges and interpreting the ranks in $\pi$ as presence times. Temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that at $p=\log n/n$ any fixed pair of vertices can a.a.s. reach each other; at $2\log n/n$ at least one vertex (and in fact, any fixed vertex) can a.a.s. reach all others; and at $3\log n/n$ all the vertices can a.a.s. reach each other, i.e., the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size $2n+o(n)$ as soon as it becomes temporally connected, which is nearly optimal as $2n-4$ is a lower bound. This result is significant because temporal graphs do not admit spanners of size $O(n)$ in general (Kempe et al, STOC 2000). In fact, they do not even admit spanners of size $o(n^2)$ (Axiotis et al, ICALP 2016). Thus, our result implies that the obstructions found in these works, and more generally, all non-negligible obstructions, must be statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners further, we show that pivotal spanners -- i.e., spanners of size $2n-2$ made of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently) -- exist a.a.s. at $4\log n/n$, this threshold being also sharp. Finally, we show that optimal spanners (of size $2n-4$) also exist a.a.s. at $p = 4\log n/n$., Comment: accepted by the SIAM Journal on Computing

Given an undirected $n$-vertex graph and $k$ pairs of terminal vertices $(s_1,t_1), \ldots, (s_k,t_k)$, the $k$-Disjoint Shortest Paths ($k$-DSP)-problem asks whether there are $k$ pairwise vertex-disjoint paths $P_1,\ldots, P_k$ such that $P_i$ is a shortest $s_i$-$t_i$-path for each $i \in [k]$. Recently, Lochet [SODA 2021] provided an algorithm that solves $k$-DSP in $n^{O(k^{5^k})}$ time, answering a 20-year old question about the computational complexity of $k$-DSP for constant $k$. On the one hand, we present an improved $n^{O(k!k)}$-time algorithm based on a novel geometric view on this problem. For the special case $k=2$ on $m$-edge graphs, we show that the running time can be further reduced to $O(nm)$ by small modifications of the algorithm and a refined analysis. On the other hand, we show that $k$-DSP is W[1]-hard with respect to $k$, showing that the dependency of the degree of the polynomial running time on the parameter $k$ is presumably unavoidable.

Several studies have found significant increase in the fatigue strength of welded joints of structural steels at sub-zero temperatures. This study addresses the research by investigating the applicability of local fatigue assessment methods to welded joints exposed to sub-zero temperatures. For this purpose, fatigue test results of two fillet weld details with weld toe and weld root failure are evaluated at a range of temperatures using a variety of structural hot-spot and notch stress approaches, then are compared to the nominal stress approach. Large differences in prediction accuracy are found for the analysed assessment methods and both failure locations.

Treewidth is arguably the most important structural graph parameter leading to algorithmically beneficial graph decompositions. Triggered by a strongly growing interest in temporal networks (graphs where edge sets change over time), we discuss fresh algorithmic views on temporal tree decompositions and temporal treewidth. We review and explain some of the recent work together with some encountered pitfalls, and we point out challenges for future research.

The classical, linear-time solvable Feedback Edge Set problem is concerned with finding a minimum number of edges intersecting all cycles in a (static, unweighted) graph. We provide a first study of this problem in the setting of temporal graphs, where edges are present only at certain points in time. We find that there are four natural generalizations of Feedback Edge Set, all of which turn out to be NP-hard. We also study the tractability of these problems with respect to several parameters (solution size, lifetime, and number of graph vertices, among others) and obtain some parameterized hardness but also fixed-parameter tractability results.