Temporal graphs have time-stamped edges. Building on previous work, we study the problem of finding a small vertex set (the separator) whose removal destroys all temporal paths between two designated ...terminal vertices. Herein, we consider two models of temporal paths: those that pass through arbitrarily many edges per time step (non-strict) and those that pass through at most one edge per time step (strict). Regarding the number of time steps of a temporal graph, we show a complexity dichotomy (NP-completeness versus polynomial-time solvability) for both problem variants. Moreover, we prove both problem variants to be NP-complete even on temporal graphs whose underlying graph is planar. Finally, we introduce the notion of a temporal core (vertices whose incident edges change over time) and prove that the non-strict variant is fixed-parameter tractable when parameterized by the temporal core size, while the strict variant remains NP-complete, even for constant-size temporal cores.
Addressing a quest by Gupta et al. (in: Proceedings of the 41st international colloquium on automata, languages, and programming (ICALP 2014), vol 8572 of LNCS. Springer, pp 563–575, 2014), we ...provide a first, comprehensive study of finding a short
s
–
t
path in the multistage graph model, referred to as the
Multistage
s
–
t
Path
problem. Herein, given a sequence of graphs over the same vertex set but changing edge sets, the task is to find short
s
–
t
paths in each graph (“snapshot”) such that in the found path sequence the consecutive
s
–
t
paths are “similar”. We measure similarity by the size of the symmetric difference of either the vertex set (vertex-similarity) or the edge set (edge-similarity) of any two consecutive paths. We prove that these two variants of
Multistage
s
–
t
Path
are already
NP
-hard for an input sequence of only two snapshots and maximum vertex degree four. Motivated by this fact and natural applications of this scenario e.g. in traffic route planning, we perform a parameterized complexity analysis. Among other results, for both variants, vertex- and edge-similarity, we prove parameterized hardness (
W1
-hardness) regarding the parameter path length (solution size). As a further conceptual investigation, we then modify the multistage model by asking for
dissimilar
consecutive paths. As one of the main technical results (employing so-called representative sets known from non-temporal settings), we prove that dissimilarity allows for fixed-parameter tractability for the parameter solution size, contrasting with our W1-hardness proof of the corresponding similarity case. We also provide partially positive results concerning efficient and effective data reduction (kernelization).
Abstract We study the problem of placing wildlife crossings, such as green bridges, over human-made obstacles to challenge habitat fragmentation. The main task herein is, given a graph describing ...habitats or routes of wildlife animals and possibilities of building green bridges, to find a low-cost placement of green bridges that connects the habitats. We develop three problem models for this task and study them from a computational complexity and parameterized algorithmics perspective.
We investigate for temporal graphs the computational complexity of separating two distinct vertices s and z by vertex deletion. In a temporal graph, the vertex set is fixed but the edges have ...(discrete) time labels. Since the corresponding Temporal(s,z)-Separation problem is NP-complete, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph—there we observe polynomial-time solvability in the case of bounded treewidth—as well as restrictions concerning the “temporal evolution” along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases.
Human development has far-reaching impacts on the surface of the globe. The transformation of natural land cover occurs in different forms, and urban growth is one of the most eminent transformative ...processes. We analyze global land cover data and extract cities as defined by maximally connected urban clusters. The analysis of the city size distribution for all cities on the globe confirms Zipf’s law. Moreover, by investigating the percolation properties of the clustering of urban areas we assess the closeness to criticality for various countries. At the critical thresholds, the urban land cover of the countries undergoes a transition from separated clusters to a gigantic component on the country scale. We study the Zipf-exponents as a function of the closeness to percolation and find a systematic dependence, which could be the reason for deviating exponents reported in the literature. Moreover, we investigate the average size of the clusters as a function of the proximity to percolation and find country specific behavior. By relating the standard deviation and the average of cluster sizes—analogous to Taylor’s law—we suggest an alternative way to identify the percolation transition. We calculate spatial correlations of the urban land cover and find long-range correlations. Finally, by relating the areas of cities with population figures we address the global aspect of the allometry of cities, finding an exponent δ ≈ 0.85, i.e., large cities have lower densities.
Parameterized aspects of triangle enumeration Bentert, Matthias; Fluschnik, Till; Nichterlein, André ...
Journal of computer and system sciences,
August 2019, 2019-08-00, Volume:
103
Journal Article
Peer reviewed
Open access
The task of listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a ...significant body of work contributing to both theoretical aspects (e.g., lower and upper bounds on running time, adaption to new computational models) as well as practical aspects (e.g. algorithms tuned for large graphs). Motivated by the fact that the worst-case running time is cubic, we perform a systematic parameterized complexity study of triangle enumeration. We provide both positive results (new enumerative kernelizations, “subcubic” parameterized solving algorithms) as well as negative results (presumable uselessness in terms of “faster” parameterized algorithms of certain parameters such as graph diameter). To this end, we introduce new and extend previous concepts.
We study the computational complexity of routing multiple objects through a network while avoiding collision: Given a graph G with two distinct terminals and two positive integers p,k, the question ...is whether one can connect the terminals by at least p routes (walks, trails, paths; the latter two without repeated edges or vertices, respectively) such that in at most k edges it happens that we traverse them in more than one route at the same time. We prove that for paths and trails the problem is NP-hard on undirected and directed planar graphs even if the maximum vertex degree or k≥0 is constant. For walks we prove polynomial-time solvability on undirected graphs for unbounded k and on directed graphs if k≥0 is constant. We additionally study variants where the maximum length of a route is restricted. For walks this variant becomes NP-hard on undirected graphs.
Averaging time series under dynamic time warping is an important tool for improving nearest-neighbor classifiers and formulating centroid-based clustering. The most promising approach poses time ...series averaging as the problem of minimizing a Fréchet function. Minimizing the Fréchet function is NP-hard and so far solved by several heuristics and inexact strategies. Our contributions are as follows: we first discuss some inaccuracies in the literature on exact mean computation in dynamic time warping spaces. Then we propose an exponential-time dynamic program for computing a global minimum of the Fréchet function. The proposed algorithm is useful for benchmarking and evaluating known heuristics. In addition, we present an exact polynomial-time algorithm for the special case of binary time series. Based on the proposed exponential-time dynamic program, we empirically study properties like uniqueness and length of a mean, which are of interest for devising better heuristics. Experimental evaluations indicate substantial deficits of state-of-the-art heuristics in terms of their output quality.
We study the NP-complete Minimum Shared Edges (MSE) problem, defined as follows. Given an undirected graph, a source and a sink vertex, and two integers p and k, we ask whether there are p paths in ...the graph connecting the source with the sink and sharing at most k edges. Herein, an edge is shared if it appears in at least two paths. On the positive side, we show that MSE is fixed-parameter tractable with respect to p. On the negative side, we show that MSE is W1 -hard when parameterized by the treewidth of the input graph and the number k of shared edges combined, and that MSE does not admit a polynomial-size kernel with respect to p (unless NP⊆coNP/poly).
PDF
