Temporal interval cliques and independent sets

作     者：Hermelin, Danny Itzhaki, Yuval Molter, Hendrik Niedermeier, Rolf 

作者机构：Bengurion Univ Negev POB 653 IL-8410501 Beer Sheva Israel TU Berlin Str 17 Juni 135 D-10623 Berlin Germany 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2023年第961卷第1期

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Israel Science Foundation [1070/20] 

主　　题：Temporal graphs Vertex orderings Order preservation Interval graphs Algorithms and complexity 

摘      要：Temporal graphs have been recently introduced to model changes in a given network that occur throughout a fixed period of time. The TEMPORAL A CLIQUE problem, which generalizes the well known CLIQUE problem to temporal graphs, has been studied in the context of finding nodes of interest in dynamic networks [TCS 16]. We introduce the TEMPORAL A INDEPENDENT SET problem, a temporal generalization of INDEPENDENT SET. This problem is e.g. motivated in the context of finding conflict-free schedules for maximum subsets of tasks, that have certain (time-varying) constraints within a given time period. We are specifically interested in the case where each task needs to be performed in a certain time-interval on each day and two tasks are in conflict on a certain day if their time-intervals on that day overlap. This leads us to consider both problems on the restricted class of temporal unit interval graphs, i.e., temporal graphs where each layer is a unit interval graph. We present several hardness results as well as positive results. On the algorithmic side, we provide constant-factor approximation algorithms for instances of both problems where t, the total number of time steps (layers) of the temporal graph, and A, a parameter that allows us to model conflict tolerance, are constants. We develop an exact FPT algorithm for TEMPORAL A CLIQUE with respect to parameter t + k. Finally, we use the notion of order preservation for temporal unit interval graphs that, informally, requires the intervals of every layer to obey a common ordering. For both problems, we provide an FPT algorithm parameterized by the size of minimum vertex deletion set to order preservation.(c) 2023 Elsevier B.V. All rights reserved.