Problem statement and complexity analysis > FDS: finding dense subgraphs find a connected temporal subgraph with the greatest cohesive density Problem hardness[bogdanov et al. 111 the FDs problem is NP-complete, even for a temporal network with a single snapshot and with +1 or-1 edge weights only Our approximation hardness result the cohesive density of the optimal dense temporal subgraph is NP-hard to approximate within any constant factor. proof sketch: building an approximation factor preserving reduction from the net worth maximization problem, which is NP- hard to approximate within any constant factor P Bogdanov, M. Mongiov, A K Singh. Mining heavy subgraphs in time-evolving networks. In /CDM, 2011. 7Problem statement and complexity analysis ➢ Problem hardness[Bogdanov et al. 11] P. Bogdanov, M. Mongiov, A. K. Singh. Mining heavy subgraphs in time-evolving networks. In ICDM, 2011. 7 ➢ Our approximation hardness result • the FDS problem is NP-complete, even for a temporal network with a single snapshot and with +1 or -1 edge weights only. • the cohesive density of the optimal dense temporal subgraph is NP-hard to approximate within any constant factor. ✓ proof sketch: building an approximation factor preserving reduction from the net worth maximization problem, which is NP￾hard to approximate within any constant factor. ➢ FDS: finding dense subgraphs • find a connected temporal subgraph with the greatest cohesive density