direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Feedback Sets in Temporal Graphs

Roman Haag (TU Berlin)

 

In this thesis, we define two temporal analogues to the well-known Feedback Edge Set problem and study their parameterized complexity. Our work is based on an established model called a temporal graph which consists of a set of vertices V , a lifetime τ ∈ N, and set of time-labeled edges E ⊆ (V2) × [τ]. The underlying graph of a temporal graph is the static graph obtained by removing all time-labels and keeping only one edge from every multi-edge. A sequence of time-labeled edges that form a closed walk in the underlying graph is called a temporal tour, if its time-labels are strictly increasing (strict case) or non-decreasing (non-strict case). We distinguish between two variants to define feedback sets, i.e., sets whose deletion makes the graph tour-free: time-edge deletion removes an edge at one specific point in time and connection deletion removes all edges between a pair of vertices. We will call the corresponding problems of finding such deletion sets with minimum cardinality (Strict) Temporal Feedback Edge Set ((S)TFES) and (Strict) Temporal Feedback Connection Set ((S)TFES), respectively.

In contrast to the polynomial-time results known for the static case, we show that (S)TFES and (S)TFCS are NP-hard and presumably do not admit an XP algorithm when parameterized by the lifetime τ of the temporal graph. For the parameter solution size k we prove W[1]-hardness for all variants. Combining both parameters, we achieve a positive result and present a simple search tree algorithm solving the strict variants STFES and STFCS in O(τ^k · |V| · |E|^2) time. Our main algorithmic contribution is a dynamic program which solves STFES in O(2^(2|V|^2) · |V|^3 · τ) time and TFES in O(2^(3|V|^2) · |V|^2 · τ) time, thus proving the fixed-parameter tractability of (S)TFES for the parameter |V| (a result which is obtained trivially for (S)TFCS).

 

Date
Speaker
Location
Language
04.07.2019
16:15
Roman Haag
TEL 512
English

Back to the research colloquium site.

To top

Zusatzinformationen / Extras