# Disentangling the Computational Complexity of Network Untangling

arXiv: https://arxiv.org/abs/2204.02668 · HTML: https://mlsanity.com/paper/2204.02668/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 49 references that are in the map.
- First posted on arXiv 6 Apr 2022.

## Builds on (most cited first, 11 of 11)

- [Node Embedding over Temporal Graphs](https://mlsanity.com/paper/1903.08889/) (2019)
- [Computing Maximum Matchings in Temporal Graphs](https://mlsanity.com/paper/1905.05304/) (2019)
- [Tight lower bounds for the complexity of multicoloring](https://mlsanity.com/paper/1607.03432/) (2016)
- [Sliding Window Temporal Graph Coloring](https://mlsanity.com/paper/1811.04753/) (2018)
- [Optimizing Reachability Sets in Temporal Graphs by Delaying](https://mlsanity.com/paper/2004.05875/) (2020)
- [On Temporal Graph Exploration](https://mlsanity.com/paper/1504.07976/) (2015)
- [The Complexity of Finding Small Separators in Temporal Graphs](https://mlsanity.com/paper/1711.00963/) (2017)
- [What is known about Vertex Cover Kernelization?](https://mlsanity.com/paper/1811.09429/) (2018)
- [How fast can we reach a target vertex in stochastic temporal graphs?](https://mlsanity.com/paper/1903.03636/) (2019)
- [Two Influence Maximization Games on Graphs Made Temporal](https://mlsanity.com/paper/2105.05987/) (2021)
- [Interference-free Walks in Time: Temporally Disjoint Paths](https://mlsanity.com/paper/2105.08335/) (2021)

## Abstract (arXiv)

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.