Combinatorial Network Abstraction by Trees and Distances

Abstract

This work draws attention to combinatorial network abstraction problems which are specified by a class P of pattern graphs and a real-valued similarity measure ϱ based on certain graph properties. For fixed P and ϱ, the optimization task on any graph G is to find a subgraph G′ which belongs to P and minimizes ϱ(G,G′). We consider this problem for the natural case of trees and distance-based similarity measures. In particular, we systematically study spanning trees of graphs that minimize distances, approximate distances, and approximate closeness-centrality with respect to some standard vector and matrix norms. The complexity analysis shows that all considered variants of the problem are NP-complete, except for the case of distance-minimization with respect to the L ∞ norm. We further show that unless P = NP, there exist no polynomial-time constant-factor approximation algorithms for the distance-approximation problems if a subset of edges can be forced into the spanning tree.