×

Linear-time certifying algorithms for near-graphical sequences. (English) Zbl 1185.05135

Summary: A sequence \(\langle d_{1},d_{2},\dots ,d_n\rangle \) of non-negative integers is graphical if it is the degree sequence of some graph, that is, there exists a graph \(G\) on \(n\) vertices whose \(i\)th vertex has degree \(d_i\), for \(1\leq i\leq n\). The notion of a graphical sequence has a natural reformulation and generalization in terms of factors of complete graphs.
If \(H=(V,E)\) is a graph and \(g\) and \(f\) are integer-valued functions on the vertex set \(V\), then a \((g,f)\)-factor of \(H\) is a subgraph \(G=(V,F)\) of \(H\) whose degree at each vertex \(v\in V\) lies in the interval \([g(v),f(v)]\). Thus, a (0,1)-factor is just a matching of \(H\) and a (1, 1)-factor is a perfect matching of \(H\). If \(H\) is complete then a \((g,f)\)-factor realizes a degree sequence that is consistent with the sequence of intervals \(\langle [g(v_{1}),f(v_{1})],[g(v_{2}),f(v_{2})],\dots ,[g(v_n),f(v_n)]\rangle \).
Graphical sequences have been extensively studied and admit several elegant characterizations. We are interested in extending these characterizations to non-graphical sequences by introducing a natural measure of “near-graphical”. We do this in the context of minimally deficient \((g,f)\)-factors of complete graphs. Our main result is a simple linear-time greedy algorithm for constructing minimally deficient \((g,f)\)-factors in complete graphs that generalizes the method of Hakimi and Havel (for constructing \((f,f)\)-factors in complete graphs, when possible). It has the added advantage of producing a certificate of minimum deficiency (through a generalization of the Erdös-Gallai characterization of \((f,f)\)-factors in complete graphs) at no additional cost.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C07 Vertex degrees
68R10 Graph theory (including graph drawing) in computer science

Software:

LEDA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anstee, R., An algorithmic proof of Tutte’s \(f\)-factor theorem, J. Algorithms, 6, 112-131 (1985) · Zbl 0562.05038
[2] Anstee, R., Simplified existence theorems for \((g, f)\)-factors, Discrete Appl. Math., 27, 29-38 (1990) · Zbl 0735.05060
[3] Arikati, S.; Maheshwari, A., Realizing degree sequences in parallel, SIAM J. Discrete Math., 9, 2, 317-338 (1996) · Zbl 0846.68044
[4] Asano, Takao, Graphical degree sequence problems with connectivity requirements, (Proc. 4th ISAAC. Proc. 4th ISAAC, LNCS, vol. 762 (1993)), 38-47 · Zbl 0925.05040
[5] Belck, H. B., Regulare factoren von graphen, J. Reine Angew. Math., 188, 228-252 (1950) · Zbl 0040.26001
[6] Berge, C., Two theorems in graph theory, Proc. Natl. Acad. Sci. USA, 43, 842-844 (1957) · Zbl 0086.16202
[7] Berge, C., Sur le couplage maximum d’un graphe, C. R. Acad. Sci. Paris, 247, 258-259 (1958) · Zbl 0086.16301
[8] Berge, C., Graphs and Hypergraphs (1973), North Holland · Zbl 0483.05029
[9] Erdös, P.; Gallai, T., Graphs with prescribed degrees of vertices, Mat. Lapok, 11, 264-272 (1960)
[10] H.N. Gabow, An efficient reduction technique for degree constrained subgraphs and bidirected network flow problems, in: Proc. 15th Annual ACM Symposium on Theory of Computing, 1983, pp. 448-456; H.N. Gabow, An efficient reduction technique for degree constrained subgraphs and bidirected network flow problems, in: Proc. 15th Annual ACM Symposium on Theory of Computing, 1983, pp. 448-456
[11] Gale, D., A theorem on flows in networks, Pacific J. Math., 7, 1073-1082 (1957) · Zbl 0087.16303
[12] Hakimi, S. L., On the realizability of a set of integers as the degrees of the vertices of a linear graph, SIAM J. Appl. Math., 10, 496-506 (1962) · Zbl 0109.16501
[13] Harary, F., Graph Theory (1969), Addison-Wesley · Zbl 0797.05064
[14] Havel, V., Eine Bemerkung uber die Existenz der endlichen Graphen, Casopis Pest. Mat., 80, 477-480 (1955) · Zbl 0068.37202
[15] Hell, P.; Kirkpatrick, D. G., Algorithms for degree constrained graph factors of minimum deficiency, J. Algorithms, 14, 115-138 (1993) · Zbl 0764.68118
[16] P. Hell, D.G. Kirkpatrick, A greedy \([ g , f ]\); P. Hell, D.G. Kirkpatrick, A greedy \([ g , f ]\)
[17] Lovasz, L., Subgraphs with prescribed valencies, J. Combin. Theory, 8, 391-416 (1970) · Zbl 0198.29201
[18] Lovasz, L.; Plummer, M. D., Matching Theory (1986), North Holland · Zbl 0618.05001
[19] Mehlhorn, K.; Näher, S., The LEDA Platform for Combinatorial and Geometric Computing (1999), Cambridge University Press · Zbl 0976.68156
[20] M. Mihail, N. Vishnoi, On Generating Graphs with Prescribed Degree Sequences for Complex Network Modeling Applications, in: Proc. 3rd Workshop on Approximation and Randomized Algorithms for Communication Networks, Rome, Italy, September 2002; M. Mihail, N. Vishnoi, On Generating Graphs with Prescribed Degree Sequences for Complex Network Modeling Applications, in: Proc. 3rd Workshop on Approximation and Randomized Algorithms for Communication Networks, Rome, Italy, September 2002
[21] Ryser, H. J., Matrices of zeros and ones, Bull. Amer. Math. Soc., 66, 442-464 (1960) · Zbl 0097.24901
[22] Shiloach, Y., Another look at the degree constrained subgraph problem, Inform. Process. Lett., 12, 89-92 (1981) · Zbl 0492.05041
[23] Takahashi, M.; Imai, K.; Asano, T., Graphical degree sequence problems, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E77-A, 3, 546-552 (1994)
[24] Tutte, W. T., The factorization of linear graphs, J. London Math. Soc., 22, 107-111 (1947) · Zbl 0029.23301
[25] Tutte, W. T., The factors of graphs, Canad. J. Math., 4, 314-328 (1952) · Zbl 0049.24202
[26] Tutte, W. T., Graph factors, Combinatorica, 1, 79-97 (1981) · Zbl 0494.05046
[27] Wasserman, H.; Blum, M., Software reliability via run-time result-checking, J. ACM, 44, 826-849 (1997) · Zbl 0904.68064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.