Document Open Access Logo

Efficiently Realizing Interval Sequences

Authors Amotz Bar-Noy, Keerti Choudhary, David Peleg, Dror Rawitz

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.47.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Amotz Bar-Noy
  • City University of New York (CUNY), USA
Keerti Choudhary
  • Weizmann Institute of Science, Rehovot, Israel
David Peleg
  • Weizmann Institute of Science, Rehovot, Israel
Dror Rawitz
  • Bar Ilan University, Ramat-Gan, Israel

Funding

US-Israel BSF grant 2018043; Army Research Laboratory Cooperative Grant, ARL Network Science CTA, W911NF-09- 2-0053.

Cite As Get BibTex

Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Efficiently Realizing Interval Sequences. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ISAAC.2019.47

Abstract

We consider the problem of realizable interval-sequences. An interval sequence comprises of n integer intervals [a_i,b_i] such that 0 <= a_i <= b_i <= n-1, and is said to be graphic/realizable if there exists a graph with degree sequence, say, D=(d_1,...,d_n) satisfying the condition a_i <= d_i <= b_i, for each i in [1,n]. There is a characterisation (also implying an O(n) verifying algorithm) known for realizability of interval-sequences, which is a generalization of the Erdös-Gallai characterisation for graphic sequences. However, given any realizable interval-sequence, there is no known algorithm for computing a corresponding graphic certificate in o(n^2) time.
In this paper, we provide an O(n log n) time algorithm for computing a graphic sequence for any realizable interval sequence. In addition, when the interval sequence is non-realizable, we show how to find a graphic sequence having minimum deviation with respect to the given interval sequence, in the same time. Finally, we consider variants of the problem such as computing the most regular graphic sequence, and computing a minimum extension of a length p non-graphic sequence to a graphic one.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Enumeration
Keywords
  • Graph realization
  • graphic sequence
  • interval sequence

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Martin Aigner and Eberhard Triesch. Realizability and uniqueness in graphs. Discrete Mathematics, 136:3-20, 1994. Google Scholar
  2. Richard Anstee. Properties of a class of (0,1)-matrices covering a given matrix. Can. J. Math., pages 438-453, 1982. Google Scholar
  3. Richard Anstee. An algorithmic proof of Tutte’s f-factor theorem. J. Algorithms, 6(1):112-131, 1985. Google Scholar
  4. M. Behzad and James E. Simpson. Eccentric sequences and eccentric sets in graphs. Discrete Mathematics, 16(3):187-193, 1976. Google Scholar
  5. Mao-cheng Cai, Xiaotie Deng, and Wenan Zang. Solution to a problem on degree sequences of graphs. Discrete Mathematics, 219(1-3):253-257, 2000. Google Scholar
  6. Wai-Kai Chen. On the realization of a (p,s)-digraph with prescribed degrees. Journal of the Franklin Institute, 281(5):406-422, 1966. Google Scholar
  7. Paul Erdös and Tibor Gallai. Graphs with Prescribed Degrees of Vertices [Hungarian]. Matematikai Lapok, 11:264-274, 1960. Google Scholar
  8. A. Frank. Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discrete Math., 5:25-43, 1992. Google Scholar
  9. A. Frank. Connectivity augmentation problems in network design. In Mathematical Programming: State of the Art, pages 34-63. Univ. Michigan, 1994. Google Scholar
  10. H. Frank and W. Chou. Connectivity considerations in the design of survivable networks. IEEE Trans. Circuit Theory, CT-17:486-490, 1970. Google Scholar
  11. Satoru Fujishige and Sachin B. Patkar. Realization of set functions as cut functions of graphs and hypergraphs. Discrete Mathematics, 226(1-3):199-210, 2001. Google Scholar
  12. D.R. Fulkerson. Zero-one matrices with zero trace. Pacific J. Math., 12:831-836, 1960. Google Scholar
  13. Ankit Garg, Arpit Goel, and Amitabha Tripathi. Constructive extensions of two results on graphic sequences. Discrete Applied Mathematics, 159(17):2170-2174, 2011. Google Scholar
  14. R.E. Gomory and T.C. Hu. Multi-terminal network flows. J. Soc. Industrial & Applied Math., 9, 1961. Google Scholar
  15. Jiyun Guo and Jianhua Yin. A variant of Niessen’s problem on degree sequences of graphs. Discrete Mathematics and Theoretical Computer Science, Vol. 16 no. 1 (in progress)(1):287-292, May 2014. Graph Theory. URL: https://hal.inria.fr/hal-01179211.
  16. S. Louis Hakimi. On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph -I. SIAM J. Appl. Math., 10(3):496-506, 1962. Google Scholar
  17. Sepp Hartung and André Nichterlein. NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs. SIAM J. Discrete Math., 29(4):1931-1960, 2015. Google Scholar
  18. V. Havel. A Remark on the Existence of Finite Graphs [in Czech]. Casopis Pest. Mat., 80:477-480, 1955. Google Scholar
  19. Katherine Heinrich, Pavol Hell, David G. Kirkpatrick, and Guizhen Liu. A simple existence criterion for g < f–factors, with applications to [a, b]–factors. Discrete Mathematics, 85:313-317, 1990. Google Scholar
  20. Pavol Hell and David G. Kirkpatrick. Linear-time certifying algorithms for near-graphical sequences. Discrete Mathematics, 309(18):5703-5713, 2009. Google Scholar
  21. Daniel J. Kleitman and D. L. Wang. Algorithms for constructing graphs and digraphs with given valences and factors. Discrete Mathematics, 6(1):79-88, 1973. Google Scholar
  22. Linda Lesniak. Eccentric sequences in graphs. Periodica Mathematica Hungarica, 6(4):287-293, 1975. Google Scholar
  23. László Lovász. Subgraphs with prescribed valencies. J. Comb. Theory, 8:391-416, 1970. Google Scholar
  24. N.V.R. Mahadev and U.N. Peled. Threshold Graphs and Related Topics. Annals of Discrete Mathematics. Elsevier Science, 1995. Google Scholar
  25. Akutsu Tatsuya and Hiroshi Nagamochi. Comparison and enumeration of chemical graphs. Computational and structural biotechnology, 5, 2013. Google Scholar
  26. Amitabha Tripathi, Sushmita Venugopalan, and Douglas B. West. A short constructive proof of the Erdos-Gallai characterization of graphic lists. Discrete Mathematics, 310(4):843-844, 2010. Google Scholar
  27. W. T. Tutte. Graph factors. Combinatorica, 1(1):79-97, March 1981. Google Scholar
  28. D.L. Wang and D.J. Kleitman. On the existence of n-connected graphs with prescribed degrees (n > 2). Networks, 3:225-239, 1973. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact