Disentangling the computational complexity of network untangling

DOI10.1007/S00224-023-10150-YMaRDI QIDQ6151149zbMATH OpenOpenAlexFDO

Authors Vincent Froese, Pascal Kunz, Philipp Zschoche

Publication date 9 February 2024

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2204.02668

zbMATH Keywords

complexity dichotomyparameterized algorithmicstemporal graph mining

Mathematics Subject Classification ID

Graph theory (05Cxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

Abstract: We study the network untangling problem introduced by Rozenshtein, Tatti, and Gionis [DMKD 2021], which is a variant of Vertex Cover on temporal graphs -- graphs whose edge set changes over discrete time steps. They introduce two problem variants. The goal is to select at most $k$ time intervals for each vertex such that all time-edges are covered and (depending on the problem variant) either the maximum interval length or the total sum of interval lengths is minimized. This problem has data mining applications in finding activity timelines that explain the interactions of entities in complex networks. Both variants of the problem are NP-hard. In this paper, we initiate a multivariate complexity analysis involving the following parameters: number of vertices, lifetime of the temporal graph, number of intervals per vertex, and the interval length bound. For both problem versions, we (almost) completely settle the parameterized complexity for all combinations of those four parameters, thereby delineating the border of fixed-parameter tractability.

Recommendations

• The network-untangling problem: from interactions to activity timelines
• Temporal vertex cover with a sliding time window
• Multistage vertex cover
• Multistage Vertex Cover
• Temporal vertex cover with a sliding time window

Cites work

• Almost 2-SAT is fixed-parameter tractable
• Bin packing with fixed number of bins revisited
• Computing maximum matchings in temporal graphs.
• Edge exploration of temporal graphs
• Finding temporal paths under waiting time constraints
• Fundamentals of parameterized complexity
• How fast can we reach a target vertex in stochastic temporal graphs?
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• Multistage graph problems on a global budget
• Multistage vertex cover
• On the complexity of k-SAT
• Optimizing reachability sets in temporal graphs by delaying
• Parameterized algorithm for eternal vertex cover
• Parameterized algorithms
• Parameterized complexity of Vertex Cover variants
• Parametrized complexity theory.
• Sliding window temporal graph coloring
• Temporal vertex cover with a sliding time window
• The complexity of finding small separators in temporal graphs
• The network-untangling problem: from interactions to activity timelines
• The node-deletion problem for hereditary properties is NP-complete
• Tight lower bounds for the complexity of multicoloring
• Traveling salesman problems in temporal graphs
• What Is Known About Vertex Cover Kernelization?

Cited in

(4)

• An FPT algorithm for timeline cover
• Exact and approximation algorithms for covering timeline in temporal graphs
• Partial temporal vertex cover with bounded activity intervals
• Temporal dominating set and temporal vertex cover under the lens of degree restrictions

This page was built for publication: Disentangling the computational complexity of network untangling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6151149)