×

Algorithms for degree constrained graph factors of minimum deficiency. (English) Zbl 0764.68118

Summary: If \(H\) is a graph and \(g\) and \(f\) are integer valued functions on the vertex set of \(H\), then a \((g,f)\)-factor of \(H\) is a subgraph \(G\) of \(H\) whose degree at each vertex \(v\) of \(H\) lies in the interval \([g(v),f(v)]\). Thus, a (0,1)-factor of \(H\) is just a matching of \(H\), and a (1,1)-factor of \(H\) is a perfect matching of \(H\). In case \(H\) admits no \((g,f)\)-factor, one may wish to find a subgraph which is “as close as possible” to being a \((g,f)\)-factor. We consider only subgraphs which are themselves \((0,f)\)-factors of \(H\) (these are clearly guaranteed to exist), and distinguish two ways in which to measure the extent to which a \((0,f)\)-factor falls short of being a \((g,f)\)-factor, i.e., to which it fails to meet the lower bounds \(g(v)\) on the degree of \(v\). The first way involves the notion of \(g\)-deficiency, which is defined to be the sum of all amounts by which the degrees of the vertices fall short of \(g(v)\). Our main result is an efficient algorithm for the construction of a \((0,f)\)-factor of \(H\) of minimum \(g\)-deficiency. When \(H\) is bipartite (or more generally, when \(g\) is uniformly less than \(f\) except on a set of vertices that induces a bipartite subgraph of \(H)\), we obtain an \(O(\sqrt{g(V)}(\| E\|+g(V)))\) algorithm by a nontrivial modification of the Hopcroft-Karp bipartite matching algorithm. (Here \(\| E\|\) denotes the number of nonparallel edges of \(H\) and \(g(V)\) is the sum of all lower bounds \(g(v)\), \(v\in V.)\) Denoting by \(p\) the number of vertices \(v\) with \(g(v)=f(v)\), we derive an \(O(\sqrt{g(V)}(\| E\|+g(V))+p\| E\|)\) algorithm for general \(H\). What distinguishes our algorithms from earlier work (such as the \(O(\sqrt{f(V)}| E|)\) algorithm of Gabow) is that they highlight the role played by the function \(g\) in the complexity of the problem; when \(g\) is substantially smaller than \(f\) our algorithms provide substantially tighter upper bounds. We establish a linear equivalence between the maximum flow problem for 0-1 networks and the minimum \(g\)- deficiency problem in bipartite graphs. This equivalence allows us to derive the best known complexity bounds on the various cases of the maximum flow problem from our algorithm. Somewhat surprizingly, it is not clear how to derive our complexity bounds from the best maximum flow algorithms. The second way to measure how well a \((0,f)\)-factor approximates a \((g,f)\)-factor is by the number of vertices \(v\) with degree at least \(g(v)\). This quantity, called the \(g\)-saturation, is to be maximized. We show that this problem is NP-hard, provided \(g\geq 3\).

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI