Finding Temporal Paths Under Waiting Time Constraints

dc.contributor.authorCasteigts, Arnaud
dc.contributor.authorHimmel, Anne-Sophie
dc.contributor.authorMolter, Hendrik
dc.contributor.authorZschoche, Philipp
dc.date.accessioned2021-12-07T07:42:43Z
dc.date.available2021-12-07T07:42:43Z
dc.date.issued2021-06-04
dc.description.abstractComputing 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 W[1]-hard when parameterized by the distance to disjoint path of the underlying graph, which implies W[1]-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.en
dc.description.sponsorshipDFG, 327762855, More Efficient Algorithms for Polynomial-Time Solvable Graph Problems (FPTinP)en
dc.description.sponsorshipDFG, 382063982, Multivariate Algorithmik temporaler Graphprobleme (MATE)en
dc.description.sponsorshipTU Berlin, Open-Access-Mittel – 2021en
dc.identifier.eissn1432-0541
dc.identifier.issn0178-4617
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/13994
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-12767
dc.language.isoenen
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.subject.ddc004 Datenverarbeitung; Informatikde
dc.subject.otherdisease spreadingen
dc.subject.otherNP-hard problemsen
dc.subject.otherparameterized algorithmsen
dc.subject.otherrestless temporal pathsen
dc.subject.othertemporal graphsen
dc.subject.othertimed feedback vertex seten
dc.subject.otherwaiting-time policiesen
dc.titleFinding Temporal Paths Under Waiting Time Constraintsen
dc.typeArticleen
dc.type.versionpublishedVersionen
dcterms.bibliographicCitation.doi10.1007/s00453-021-00831-wen
dcterms.bibliographicCitation.issue9en
dcterms.bibliographicCitation.journaltitleAlgorithmicaen
dcterms.bibliographicCitation.originalpublishernameSpringer Natureen
dcterms.bibliographicCitation.originalpublisherplaceNew York, NYen
dcterms.bibliographicCitation.pageend2802en
dcterms.bibliographicCitation.pagestart2754en
dcterms.bibliographicCitation.volume83en
tub.accessrights.dnbfreeen
tub.affiliationFak. 4 Elektrotechnik und Informatik::Inst. Softwaretechnik und Theoretische Informatik::FG Algorithmik und Komplexitätstheoriede
tub.affiliation.facultyFak. 4 Elektrotechnik und Informatikde
tub.affiliation.groupFG Algorithmik und Komplexitätstheoriede
tub.affiliation.instituteInst. Softwaretechnik und Theoretische Informatikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
Casteigts_etal_2021_pdf.pdf
Size:
4.21 MB
Format:
Adobe Portable Document Format
Description:

Collections