Skip to main content
SpringerLink
Log in

Recognizing d-Interval Graphs and d-Track Interval Graphs

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

A d-interval is the union of d disjoint intervals on the real line. A d-track interval is the union of d disjoint intervals on d disjoint parallel lines called tracks, one interval on each track. As generalizations of the ubiquitous interval graphs, d-interval graphs and d-track interval graphs have wide applications, traditionally to scheduling and resource allocation, and more recently to bioinformatics. In this paper, we prove that recognizing d-track interval graphs is NP-complete for any constant d≥2. This confirms a conjecture of Gyárfás and West in 1995. Previously only the complexity of the case d=2 was known. Our proof in fact implies that several restricted variants of this graph recognition problem, i.e., recognizing balanced d-track interval graphs, unit d-track interval graphs, and (2,…,2) d-track interval graphs, are all NP-complete. This partially answers another question recently raised by Gambette and Vialette. We also prove that recognizing depth-two 2-track interval graphs is NP-complete, even for the unit case. In sharp contrast, we present a simple linear-time algorithm for recognizing depth-two unit d-interval graphs. These and other results of ours give partial answers to a question of West and Shmoys in 1984 and a similar question of Gyárfás and West in 1995. Finally, we give the first bounds on the track number and the unit track number of a graph in terms of the number of vertices, the number of edges, and the maximum degree, and link the two numbers to the classical concepts of arboricity.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Notes

  1. Our results remain valid even if the intervals are all closed, all left-open-right-closed, or all right-open-left-closed. The only detail that needs attention is that the restriction (x 1,…,x d ) for closed intervals corresponds to the restriction (x 1+1,…,x d +1) for open intervals.

  2. Note that unit and (x,x) 2-track interval graphs are subclasses of unit and (x,x) 2-interval graphs.

  3. Our result is indeed much stronger than what Gyárfás and West [17] originally conjectured.

  4. We remark that to ensure this covering property we only need to let y be adjacent to x. Nevertheless, we also connect y to two neighbors of x so that the graph X 4(y) has not just any 2-track interval representation, but a more restricted (2,2) 2-track interval representation following the pattern in Fig. 6. For the same reason, we connect q i to not one but three vertices p 2i−1, p 2i , and p 2i+1.

  5. A reviewer of an earlier version of this paper noted that this result may also be obtained by graph orientation techniques [4, 7].

References

  1. Akiyama, J., Exoo, G., Harary, F.: Covering and packing in graphs III: cyclic and acyclic invariants. Math. Slovaca 30, 405–417 (1980)

    MathSciNet  MATH  Google Scholar 

  2. Alcón, L., Cerioli, M.R., de Figueiredo, C.M.H., Gutierrez, M., Meidanis, J.: Tree loop graphs. Discrete Appl. Math. 155, 686–694 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  3. Alon, N.: The linear arboricity of graphs. Isr. J. Math. 62, 311–325 (1988)

    Article  MATH  Google Scholar 

  4. Alon, N., Tarsi, M.: Coloring and orientation of graphs. Combinatorica 12, 125–134 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  5. Andreae, T.: On the unit interval number of a graph. Discrete Appl. Math. 22, 1–7 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bafna, V., Narayanan, B., Ravi, R.: Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles). Discrete Appl. Math. 71, 41–53 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  7. Balogh, J., Pluhár, A.: A sharp edge bound on the interval number of a graph. J. Graph Theory 32, 153–159 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  8. Bar-Yehuda, R., Halldórsson, M.M., Naor, J.S., Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM J. Comput. 36, 1–15 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  9. Butman, A., Hermelin, D., Lewenstein, M., Rawitz, D.: Optimization problems in multiple-interval graphs. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’07), pp. 268–277 (2007)

    Google Scholar 

  10. Chen, Z., Fu, B., Jiang, M., Zhu, B.: On recovering syntenic blocks from comparative maps. J. Comb. Optim. 18, 307–318 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  11. Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P.: Simple linear time recognition of unit interval graphs. Inf. Process. Lett. 55, 99–104 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  12. Crochemore, M., Hermelin, D., Landau, G.M., Rawitz, D., Vialette, S.: Approximating the 2-interval pattern problem. Theor. Comput. Sci. 395, 283–297 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  13. Gambette, P., Vialette, S.: On restrictions of balanced 2-interval graphs. In: Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG’07). Springer LNCS, vol. 4769, pp. 55–65 (2007)

    Chapter  Google Scholar 

  14. Goldberg, A.V., Rao, S.: Beyond the flow decomposition barrier. J. ACM 45, 783–797 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  15. Griggs, J.R.: Extremal values of the interval number of a graph, II. Discrete Math. 28, 37–47 (1979)

    Article  MathSciNet  Google Scholar 

  16. Griggs, J.R., West, D.B.: Extremal values of the interval number of a graph. SIAM J. Algebr. Discrete Methods 1, 1–7 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  17. Gyárfás, A., West, D.B.: Multitrack interval graphs. Congr. Numer. 109, 109–116 (1995)

    MathSciNet  MATH  Google Scholar 

  18. Halldórsson, M.M., Karlsson, R.K.: Strip graphs: recognition and scheduling. In: Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG’06). Springer LNCS, vol. 4271, pp. 137–146 (2007)

    Chapter  Google Scholar 

  19. Jiang, M.: Approximation algorithms for predicting RNA secondary structures with arbitrary pseudoknots. IEEE/ACM Trans. Comput. Biol. Bioinform. 7, 323–332 (2010)

    Article  Google Scholar 

  20. Jiang, M.: Recognizing d-interval graphs and d-track interval graphs. In: Proceedings of the 4th International Frontiers of Algorithmics Workshop (FAW’10). Springer LNCS, vol. 6213, pp. 160–171 (2010)

    Chapter  Google Scholar 

  21. Jiang, M.: On the parameterized complexity of some optimization problems related to multiple-interval graphs. Theor. Comput. Sci. 411, 4253–4262 (2010)

    Article  MATH  Google Scholar 

  22. Jiang, M.: Inapproximability of maximal strip recovery. Theor. Comput. Sci. 412, 3759–3774 (2011)

    Article  MATH  Google Scholar 

  23. Joseph, D., Meidanis, J., Tiwari, P.: Determining DNA sequence similarity using maximum independent set algorithms for interval graphs. In: Proceedings of the 3rd Scandinavian Workshop on Algorithm Theory (SWAT’92). Springer LNCS, vol. 621, pp. 326–337 (1992)

    Google Scholar 

  24. Kumar, N., Deo, N.: Multidimensional interval graphs. Congr. Numer. 102, 45–56 (1994)

    MathSciNet  MATH  Google Scholar 

  25. Maas, C.: Determining the interval number of a triangle-free graph. Computing 31, 347–354 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  26. Peroche, B.: Complexité de l’arboricité linéaire d’un graphe. RAIRO. Rech. Opér. 16, 125–129 (1982)

    MathSciNet  MATH  Google Scholar 

  27. Roberts, F.S.: Graph Theory and Its Applications to Problems of Society. SIAM, Philadelphia (1987)

    Google Scholar 

  28. Shermer, T.C.: On rectangle visibility graphs III, external visibility and complexity. In: Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG’96), pp. 234–239 (1996)

    Google Scholar 

  29. Tarjan, R.E.: Data Structures and Network Algorithms. SIAM, Philadelphia (1983)

    Book  Google Scholar 

  30. Trotter, W.T. Jr., Harary, F.: On double and multiple interval graphs. J. Graph Theory 3, 205–211 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  31. Vialette, S.: On the computational complexity of 2-interval pattern matching problems. Theor. Comput. Sci. 312, 223–249 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  32. West, D.B.: A short proof of the degree bound for interval number. Discrete Math. 73, 309–310 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  33. West, D.B., Shmoys, D.B.: Recognizing graphs with fixed interval number is NP-complete. Discrete Appl. Math. 8, 295–305 (1984)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgement

Supported in part by NSF grant DBI-0743670. A preliminary version [20] of this paper appeared in the Proceedings of the 4th International Frontiers of Algorithmics Workshop (FAW 2010), pages 160–171.

The author would like to thank the anonymous reviewers for careful reading and thoughtful comments. In particular, the author is grateful for a penetrating remark that reveals the connected condition in Lemma 5 which was overlooked first in [32] and subsequently in the preliminary version of this paper [20].

Author information

Authors and Affiliations

  1. Department of Computer Science, Utah State University, Logan, UT, 84322, USA

    Minghui Jiang

Authors
  1. Minghui Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Minghui Jiang.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Jiang, M. Recognizing d-Interval Graphs and d-Track Interval Graphs. Algorithmica 66, 541–563 (2013). https://doi.org/10.1007/s00453-012-9651-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-012-9651-5

Keywords

Search

Navigation