Minimum Transactions Problem

摘要

We are given a directed graph G(V, E) on n vertices and m edges where each edge has a positive weight associated with it. The influx of a vertex is defined as the difference between the sum of the weights of edges entering the vertex and the sum of the weights of edges leaving the vertex. The goal is to find a graph G'(V, E') such that the influx of each vertex in G'(V, E') is same as the influx of each vertex in G(V, E) and ∣E'∣ is minimal. We show that 1. finding the optimal solution for this problem is NP-hard, 2. the optimal solution has at most n - 1 edges, and we give an algorithm to find one such solution with at most n-1 edges in O(m log n) time, and 3. for one variant of the problem where we can delete as well as add extra edges to the graph, we can compute a solution that is within a factor 3/2 from the optimal solution.