Disentangling the Computational Complexity of Network Untangling

• URL: http://arxiv.org/abs/2204.02668v1
• Date: Wed, 6 Apr 2022 08:32:39 GMT
• Title: Disentangling the Computational Complexity of Network Untangling
• Abstract summary: We study the network untangling problem introduced by Rozenshtein, Tatti, and Gionis. This problem has data mining applications in finding activity timelines that explain the interactions of entities in complex networks.
• Score: 2.127049691404299
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• HGTS-Former: Hierarchical HyperGraph Transformer for Multivariate Time Series Analysis [14.388097471205102]
  This paper proposes a novel hypergraph-based time series transformer backbone network, termed HGTS-Former.<n>We first normalize and embed each patch into tokens. Then, we adopt the multi-head self-attention to enhance the temporal representation of each patch.<n>The hierarchical hypergraphs are constructed to aggregate the temporal patterns within each channel and fine-grained relations between different variables.
  arXiv  Detail & Related papers  (2025-08-04T13:33:28Z)
• Approximating Optimal Labelings for Temporal Connectivity [7.394099294390271]
  We study the problem of scheduling the availability time of the edges of a temporal graph in such a way that all pairs of vertices are connected within a given maximum allowed time $a$. The problem, known as emphMinimum Aged Labeling (MAL), has several applications in logistics, distribution scheduling, and information spreading in social networks.
  arXiv  Detail & Related papers  (2025-04-23T16:00:33Z)
• The Complexity of Envy-Free Graph Cutting [44.58084909019557]
  We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, and every agent must be assigned a connected piece of this graph. The problem is NP-complete, and we analyze its complexity with respect to two natural complexity measures: the number of agents and the number of edges in the graph.
  arXiv  Detail & Related papers  (2023-12-12T07:54:30Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  We prove that the hardness of approximation of ReLU networks not only mirrors the complexity of the Max-Cut problem but also, in certain special cases, exactly corresponds to it. In particular, when $epsilonleqsqrt84/83-1approx 0.006$, we show that it is NP-hard to find an approximate global dataset of the ReLU network objective with relative error $epsilon$ with respect to the objective value.
  arXiv  Detail & Related papers  (2023-11-18T04:41:07Z)
• Fully-Connected Spatial-Temporal Graph for Multivariate Time-Series Data [50.84488941336865]
  We propose a novel method called Fully- Spatial-Temporal Graph Neural Network (FC-STGNN) For graph construction, we design a decay graph to connect sensors across all timestamps based on their temporal distances. For graph convolution, we devise FC graph convolution with a moving-pooling GNN layer to effectively capture the ST dependencies for learning effective representations.
  arXiv  Detail & Related papers  (2023-09-11T08:44:07Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  Temporal graphs exhibit dynamic interactions between nodes over continuous time. We propose a novel method of temporal graph convolution with the whole neighborhood. Our proposed TAP-GNN outperforms existing temporal graph methods by a large margin in terms of both predictive performance and online inference latency.
  arXiv  Detail & Related papers  (2023-04-15T08:17:18Z)
• Are uGLAD? Time will tell! [4.005044708572845]
  We introduce a novel approach for multivariate time series segmentation using conditional independence (CI) graphs. CI graphs are probabilistic graphical models that represents the partial correlations between the nodes. We demonstrate successful empirical results on a Physical Activity Monitoring data.
  arXiv  Detail & Related papers  (2023-03-21T07:46:28Z)
• TimesNet: Temporal 2D-Variation Modeling for General Time Series Analysis [80.56913334060404]
  Time series analysis is of immense importance in applications, such as weather forecasting, anomaly detection, and action recognition. Previous methods attempt to accomplish this directly from the 1D time series. We ravel out the complex temporal variations into the multiple intraperiod- and interperiod-variations.
  arXiv  Detail & Related papers  (2022-10-05T12:19:51Z)
• Convolutional Neural Networks for Time-dependent Classification of Variable-length Time Series [4.068599332377799]
  Time series data are often obtained only within a limited time range due to interruptions during observation process. To classify such partial time series, we need to account for 1) the variable-length data drawn from 2) different timestamps. Existing convolutional neural networks use global pooling after convolutional layers to cancel the length differences. This architecture suffers from the trade-off between incorporating entire temporal correlations in long data and avoiding feature collapse for short data.
  arXiv  Detail & Related papers  (2022-07-08T07:15:13Z)
• Triformer: Triangular, Variable-Specific Attentions for Long Sequence Multivariate Time Series Forecasting--Full Version [50.43914511877446]
  We propose a triangular, variable-specific attention to ensure high efficiency and accuracy. We show that Triformer outperforms state-of-the-art methods w.r.t. both accuracy and efficiency.
  arXiv  Detail & Related papers  (2022-04-28T20:41:49Z)
• Spatio-Temporal Joint Graph Convolutional Networks for Traffic Forecasting [75.10017445699532]
  Recent have shifted their focus towards formulating traffic forecasting as atemporal graph modeling problem. We propose a novel approach for accurate traffic forecasting on road networks over multiple future time steps.
  arXiv  Detail & Related papers  (2021-11-25T08:45:14Z)
• Event2Graph: Event-driven Bipartite Graph for Multivariate Time-series Anomaly Detection [25.832983667044708]
  We propose a dynamic bipartite graph structure to encode the inter-dependencies between time-series. Based on this design, relations between time series can be explicitly modelled via dynamic connections to event nodes.
  arXiv  Detail & Related papers  (2021-08-15T17:50:37Z)
• Optimizing Reachability Sets in Temporal Graphs by Delaying [8.122270502556374]
  temporal graph is a dynamic graph where every edge is assigned a set of integer time labels. We study how changes of the time labels, corresponding to delays on the availability of the edges, affect the reachability sets from given sources.
  arXiv  Detail & Related papers  (2020-04-13T11:36:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.