Another Easy Proof of NP-Completeness on the Maximum Integral Vertex-Balanced Flow Problem

概要

論文の詳細を見る
The maximum vertex-balanced flow problem of a two terminal network N is the problem of finding a maximum vertex-balanced flow, which can be regarded as a maximum flow with an additional constraint described in terms of a function, called a vertex-balancing rate function α : V- {s}→R_+- {0} where V is the vertex set and s is the source of N, and R_+ is the set of nonnegative real numbers. Especially, we consider Problem L of finding the maximum integral vertex-balanced flow of the network N, which is defined as the maximum vertex-balanced flow satisfying that the value of each arc-flow of the network N is integral. No algorithms are known for the maximum vertex-balanced flow problem, but recently we have proved that the problem L is NP-complete, i.e., L is in class NP and that every problem in NP is reducible to L in polynomial-time, where NP is a class of problems that can be solved by nondeterministic Turing machine in polynomial-time. In this paper we give another easy proof on NP-completeness of the problem L. Our proof is obtained from the transformation of SUBSET SUM, where SUBSET SUM is a yes-no problem of finding whether there is a subset S'⊂S such that Σ{s(e):eεS'}=I on condition that a positive integer I, a finite set S and positive integers s(e) (eεS') are given.
小樽商科大学の論文