POSI-MODULAR SYSTEMS WITHMODULOTONE REQUIREMENTS UNDERPERMUTATION CONSTRAINTS

摘要

Given a system (V, f, r) on a finite set V consisting of a posi-modular function f : 2~v-Rand a modulotone function r : 2~v-R, we consider the problem of finding a minimumset R C V such that f (X) > r(X) for all X C V - R. The problem, called the transversalproblem, was introduced in [M. Sakashita, K. Makino, H. Nagamochi and S. Fujishige,Minimum transversals in posi-modular systems, SIAM J. Discrete Math. 23 (2009) 858--871] as a natural generalization of the source location problem and external networkproblem with edge-connectivity requirements in undirected graphs and hypergraphs. By generalizing [H. Tamura, H. Sugawara, M. Sengoku and S. Shinoda, Plural coverproblem on undirected flow networks, IEICE Trans. J81-A (1998) 863-869] for thesource location problem, we show that the transversal problem can be solved by a simplegreedy algorithm if r is monotone, where a modulotone function r is monotone ifthere exists a permutation of V such that the function p_r : V x 2~v-R associatedwith r satisfies p_r(u,W) > p_r(v,for allWC V and u, v E with (u) v).Here we show that any modulotone function r can be characterized by p_r asr(X) W) | v E X C V - W}. We also show the structural properties on the minimal deficient sets W for thetransversal problem for 7-monotone function r, i.e., there exists a basic tree T for I/Vsuch that 7r(u) < 7r(v) for all arcs (u, v) in T, which, as a corollary, gives an alternativeproof for the correctness of the greedy algorithm for the source location problem.Furthermore, we show that a fractional version of the transversal problem can hesolved by the algorithm similar to the one for the transversal problem.