Minimum vertex weighted deficiency of \((g,f)\)-factors: A greedy algorithm (Q686268)

Given a graph \(G=(V,E)\) and integer functions \(g,f\) on \(V\), a \((g,f)\)- factor of \(G\) is a spanning subgraph \(F\) of \(G\) in which the degree of every vertex \(v\) satisfies \(g(v)\leq\text{deg}_ F(v)\leq f(v)\). If \(F\) is any spanning subgraph of \(G\), the deficiency of \(F\) is the sum over all \(v\in V\) of the quantities \(\max(0,\text{deg}_ F(v)-f(v))+\max(0,g(v)- \text{deg}_ F(v))\). The fact that a minimum deficiency subgraph \(F\) can be found in polynomial time is due to \textit{L. Lovász} [J. Comb. Theory 8, 391-416 (1970; Zbl 0198.292)]; more efficient algorithms have been proposed by \textit{H. N. Gabow} [Proc. 15th Annual ACM STOC, 448-456 (1983)] and \textit{P. Hell} and \textit{D. G. Kirkpatrick} [J. Algorithms 14, No. 1, 115-138 (1993; Zbl 0764.68118)]. The author extends the problem in two ways: Firstly, the penalty for violating the constraint \(g(v)\leq\text{deg}_ F(v)\leq f(v)\) is different for each vertex--- \(\text{below}(v)\) and \(\text{above}(v)\) are given positive quantities and the deficiency is the sum, over all \(v\in V\), of the quantities \(\text{above}(v)\times\max(0,\text{deg}_ F(v)- f(v))+\text{below}(v)\times\max(0,g (v)-\text{deg}_ F(v))\). Secondly, the graph \(G\) is allowed to have multiple edges (and loops). The proposed algorithm is polynomial in \(| V|\), regardless of the number of edges. It first constructs a fractional subgraph by network flow methods, and then transforms the fractional solution to a true subgraph by a greedy technique. More general cost functions are also considered.