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.
Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex ...set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or
temporal
, if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration
Δ
, referred to as
Δ
-
restless temporal paths
. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the “restless variant” of this problem becomes computationally hard even in very restrictive settings. For example, it is W1-hard when parameterized by the
distance to disjoint path
of the underlying graph, which implies W1-hardness for many other parameters like feedback vertex number and pathwidth. A natural question is thus whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three
kinds
of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called
timed feedback vertex number
, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work.
We investigate the computational complexity of finding
temporally disjoint
paths and walks in temporal graphs. There, the edge set changes over discrete time steps. Temporal paths and walks use edges ...that appear at monotonically increasing time steps. Two paths (or walks) are temporally disjoint if they never visit the same vertex at the same time; otherwise, they interfere. This reflects applications in robotics, traffic routing, or finding safe pathways in dynamically changing networks. At one extreme, we show that on general graphs the problem is computationally hard. The path version is NP-hard even if we want to find only two temporally disjoint paths. The walk version is W-hard (Klobas in IJCAI 4090–4096, 2021) when parameterized by the number of walks. However, it is polynomial-time solvable for any constant number of walks. At the other extreme, restricting the input temporal graph to have a path as underlying graph, quite counter-intuitively, we find NP-hardness in general but also identify natural tractable cases.
We introduce a dynamic version of the NP-hard graph modification problem
Cluster Editing
. The essential point here is to take into account dynamically evolving input graphs: having a cluster graph ...(that is, a disjoint union of cliques) constituting a solution for a first input graph, can we cost-efficiently transform it into a “similar” cluster graph that is a solution for a second (“subsequent”) input graph? This model is motivated by several application scenarios, including incremental clustering, the search for compromise clusterings, or also local search in graph-based data clustering. We thoroughly study six problem variants (three modification scenarios edge editing, edge deletion, edge insertion; each combined with two distance measures between cluster graphs). We obtain both fixed-parameter tractability as well as (parameterized) hardness results, thus (except for three open questions) providing a fairly complete picture of the parameterized computational complexity landscape under the two perhaps most natural parameterizations: the distances of the new “similar” cluster graph to (1) the second input graph and to (2) the input cluster graph.
Complex interactive test items are becoming more widely used in assessments. Being computer-administered, assessments using interactive items allow logging time-stamped action sequences. These ...sequences pose a rich source of information that may facilitate investigating how examinees approach an item and arrive at their given response. There is a rich body of research leveraging action sequence data for investigating examinees’ behavior. However, the associated timing data have been considered mainly on the item-level, if at all. Considering timing data on the action-level in addition to action sequences, however, has vast potential to support a more fine-grained assessment of examinees’ behavior. We provide an approach that jointly considers action sequences and action-level times for identifying common response processes. In doing so, we integrate tools from clickstream analyses and graph-modeled data clustering with psychometrics. In our approach, we (a) provide similarity measures that are based on both actions and the associated action-level timing data and (b) subsequently employ cluster edge deletion for identifying homogeneous, interpretable, well-separated groups of action patterns, each describing a common response process. Guidelines on how to apply the approach are provided. The approach and its utility are illustrated on a complex problem-solving item from PIAAC 2012.
We study the NP-hard graph problem
Collapsed k-Core
where, given an undirected graph
G
and integers
b
,
x
, and
k
, we are asked to remove
b
vertices such that the
k
-core of remaining graph, that ...is, the (uniquely determined) largest induced subgraph with minimum degree
k
, has size at most
x
.
Collapsed k-Core
was introduced by Zhang et al. (
2017
) and it is motivated by the study of engagement behavior of users in a social network and measuring the resilience of a network against user drop outs.
Collapsed k-Core
is a generalization of
r-Degenerate Vertex Deletion
(which is known to be NP-hard for all
r
≥ 0) where, given an undirected graph
G
and integers
b
and
r
, we are asked to remove
b
vertices such that the remaining graph is
r
-degenerate, that is, every its subgraph has minimum degree at most
r
. We investigate the parameterized complexity of
Collapsed k-Core
with respect to the parameters
b
,
x
, and
k
, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity of
Collapsed k-Core
for
k
≤ 2 and
k
≥ 3. For the latter case it is known that for all
x
≥ 0
Collapsed k-Core
is WP-hard when parameterized by
b
. For
k
≤ 2 we show that
Collapsed k-Core
is W1-hard when parameterized by
b
and in FPT when parameterized by (
b
+
x
). Furthermore, we outline that
Collapsed k-Core
is in FPT when parameterized by the treewidth of the input graph and presumably does not admit a polynomial kernel when parameterized by the vertex cover number of the input graph.
•The paper introduces the problem “Restless Temporal Separation”, which asks whether all temporal paths between two vertices s and z in a temporal path that obey certain waiting time constraints can ...be destroyed by deleting at most k vertices from the temporal graph.•Restless Temporal Separation is Σ2P-complete.•Restless Temporal Separation parameterized by the separator size is para-coNP-hard and W2-hard.
In this work, we investigate the computational complexity of Restless Temporal(s,z)-Separation, where we are asked whether it is possible to destroy all restless temporal paths between two distinct vertices s and z by deleting at most k vertices from a temporal graph. A temporal graph has a fixed vertex set but the edges have (discrete) time stamps. A restless temporal path uses edges with non-decreasing time stamps and the time spent at each vertex must not exceed a given duration Δ.
Restless Temporal(s,z)-Separation naturally generalizes the NP-hard Temporal(s,z)-Separation problem. We show that Restless Temporal(s,z)-Separation is complete for Σ2P, a complexity class located in the second level of the polynomial time hierarchy. We further provide some insights in the parameterized complexity of Restless Temporal(s,z)-Separation parameterized by the separator size k.
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.
h -Index manipulation by undoing merges van Bevern, René; Komusiewicz, Christian; Molter, Hendrik ...
Quantitative science studies,
12/2020, Letnik:
1, Številka:
4
Journal Article
Recenzirano
Odprti dostop
The
-index is an important bibliographic measure used to assess the performance of researchers. Dutiful researchers merge different versions of their articles in their Google Scholar profile even ...though this can decrease their
-index. In this article, we study the manipulation of the
-index by undoing such merges. In contrast to manipulation by merging articles, such manipulation is harder to detect. We present numerous results on computational complexity (from linear-time algorithms to parameterized computational hardness results) and empirically indicate that at least small improvements of the
-index by splitting merged articles are unfortunately easily achievable.
PDF
