Extremal Solutions for Network Flow with Differential Constraints
研究了同时有微分约束和流量守恒约束的网络流问题，证明了极值点与图论结构（生成树的推广）的对应关系，并指出在特殊情况下该对应可能失效，且判断是否失效是NP难的。
Abstract In network flow problems, there is a well-known one-to-one relationship between extreme points of the feasibility region and trees in the associated undirected graph. The same is true for the dual differential problem. In this paper, we study a problem variant with both differential constraints and constraints on flow conservation at every node, which we call differential flow . This variant is motivated by an application in the expansion planning of energy networks. We show that all extreme points in the differential flow polytope still directly correspond to graph-theoretical structures in the underlying network, namely a generalization of spanning trees. The reverse is generally also true except in very special cases where the network parameters satisfy a set of particular equations. We furthermore show that these exceptional cases can never occur in cactus graphs and present additional, sufficient criteria for when the one-to-one correspondence between extreme points and graph-theoretical structures holds. Finally, we show that it is generally NP-hard to decide for a specific network whether the graph-theoretical characterization holds for all extreme points.