Abstract
We initiate the study of a new parameterization of graph problems. In a multiple interval representation of a graph, each vertex is associated to at least one interval of the real line, with an edge between two vertices if and only if an interval associated to one vertex has a nonempty intersection with an interval associated to the other vertex. A graph on n vertices is a k-gap interval graph if it has a multiple interval representation with at most n + k intervals in total. In order to scale up the nice algorithmic properties of interval graphs (where k = 0), we parameterize graph problems by k, and find FPT algorithms for several problems, including Feedback Vertex Set, Dominating Set, Independent Set, Clique, Clique Cover, and Multiple Interval Transversal. The Coloring problem turns out to be -hard and we design an XP algorithm for the recognition problem.
Serge Gaspers and Stefan Szeider acknowledge support from the European Research Council (COMPLEX REASON, 239962). Petr Golovach acknowledges the support by EPSRC (EP/G043434/1), Royal Society (JP100692). Karol Suchan acknowledges support from Conicyt Chile (Anillo ACT-88, Basal-CMM, Fondecyt 11090390).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alon, N.: Piercing d-intervals. Discret. Comput. Geom. 19(3), 333–334 (1998)
Andreae, T.: On an extremal problem concerning the interval number of a graph. Discrete Appl. Math. 14(1), 1–9 (1986)
Andreae, T., Aigner, M.: The total interval number of a graph. J. Comb. Theory Ser. B 46(1), 7–21 (1989)
Aumann, Y., Lewenstein, M., Melamud, O., Pinter, R.Y., Yakhini, Z.: Dotted interval graphs and high throughput genotyping. In: SODA 2005, pp. 339–348 (2005)
Bafna, V., Narayanan, B.O., Ravi, R.: Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles). Discrete Appl. Math. 71(1-3), 41–53 (1996)
Balogh, J., Ochem, P., Pluhár, A.: On the interval number of special graphs. J. Graph Theor. 46(4), 241–253 (2004)
Bar-Yehuda, R., Halldórsson, M.M., Naor, J., Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM J. Comput. 36(1), 1–15 (2006)
Bar-Yehuda, R., Rawitz, D.: Using fractional primal-dual to schedule split intervals with demands. Discrete Optim. 3(4), 275–287 (2006)
Belmonte, R., Vatshelle, M.: Graph Classes with Structured Neighborhoods and Algorithmic Applications. In: Kolman, P., Kratochvíl, J. (eds.) WG 2011. LNCS, vol. 6986, pp. 47–58. Springer, Heidelberg (2011)
Bessière, C., Hebrard, E., Hnich, B., Kiziltan, Z., Quimper, C.-G., Walsh, T.: The parameterized complexity of global constraints. In: AAAI 2008, pp. 235–240 (2008)
Blin, G., Fertin, G., Vialette, S.: Extracting constrained 2-interval subsets in 2-interval sets. Theor. Comput. Sci. 385(1-3), 241–263 (2007)
Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1-2), 1–45 (1998)
Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Comput. System Sci. 13(3), 335–379 (1976)
Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Boolean-width of graphs. Theor. Comput. Sci. 412(39), 5187–5204 (2011)
Butman, A., Hermelin, D., Lewenstein, M., Rawitz, D.: Optimization problems in multiple-interval graphs. ACM Trans. Algorithms 6(2) (2010)
Catlin, P.A.: Supereulerian graphs: A survey. J. Graph Theor. 16(2), 177–196 (1992)
Chen, E., Yang, L., Yuan, H.: Improved algorithms for largest cardinality 2-interval pattern problem. J. Comb. Optim. 13(3), 263–275 (2007)
Chen, M., Chang, G.J.: Total interval numbers of complete r-partite graphs. Discrete Appl. Math. 122, 83–92 (2002)
Courcelle, B.: The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues. Rairo - Theor. Inform. Appl. 26, 257–286 (1992)
Crochemore, M., Hermelin, D., Landau, G.M., Rawitz, D., Vialette, S.: Approximating the 2-interval pattern problem. Theor. Comput. Sci. 395(2-3), 283–297 (2008)
Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer (1999)
Erdös, P., West, D.B.: A note on the interval number of a graph. Discrete Math. 55(2), 129–133 (1985)
Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410, 53–61 (2009)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series XIV. Springer (2006)
Fomin, F.V., Gaspers, S., Golovach, P., Suchan, K., Szeider, S., van Leeuwen, E.J., Vatshelle, M., Villanger, Y.: k-gap interval graphs. arXiv CoRR 1112.3244 (2011)
Gambette, P., Vialette, S.: On Restrictions of Balanced 2-Interval Graphs. In: Brandstädt, A., Kratsch, D., Müller, H. (eds.) WG 2007. LNCS, vol. 4769, pp. 55–65. Springer, Heidelberg (2007)
Gaspers, S., Szeider, S.: Kernels for global constraints. In: IJCAI 2011, pp. 540–545 (2011)
Golumbic, M.C.: Algorithmic graph theory and perfect graphs. Academic Press (1980)
Griggs, J.R., West, D.B.: Extremal values of the interval number of a graph. SIAM J. Algebra. Discr. 1(1), 1–7 (1980)
Hassin, R., Segev, D.: Rounding to an integral program. Oper. Res. Lett. 36(3), 321–326 (2008)
Jansen, B.M.P., Kratsch, S.: Data Reduction for Graph Coloring Problems. In: Owe, O., Steffen, M., Telle, J.A. (eds.) FCT 2011. LNCS, vol. 6914, pp. 90–101. Springer, Heidelberg (2011)
Jiang, M., Zhang, Y.: Parameterized Complexity in Multiple-interval Graphs: Domination. In: Rossmanith, P. (ed.) IPEC 2011. LNCS, vol. 7112, pp. 27–40. Springer, Heidelberg (2012)
Jiang, M., Zhang, Y.: Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy. In: Fu, B., Du, D.-Z. (eds.) COCOON 2011. LNCS, vol. 6842, pp. 62–73. Springer, Heidelberg (2011)
Kaiser, T.: Transversals of d-intervals. Discret. Comput. Geom. 18(2) (1997)
Kloks, T.: Treewidth, Computations and Approximations. LNCS, vol. 842. Springer, Heidelberg (1994)
Kostochka, A.V., West, D.B.: Total interval number for graphs with bounded degree. J. Graph Theor. 25(1), 79–84 (1997)
Kratzke, T.M., West, D.B.: The total interval number of a graph, I: Fundamental classes. Discrete Math. 118(1-3), 145–156 (1993)
Kratzke, T.M., West, D.B.: The total interval number of a graph II: Trees and complexity. SIAM J. Discrete Math. 9(2), 339–348 (1996)
Marx, D.: Parameterized coloring problems on chordal graphs. Theor. Comput. Sci. 351(3), 407–424 (2006)
Marx, D.: Chordal deletion is fixed-parameter tractable. Algorithmica 57(4), 747–768 (2010)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press (2006)
Raychaudhuri, A.: The total interval number of a tree and the hamiltonian completion number of its line graph. Inform. Process. Lett. 56(6), 299–306 (1995)
Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266–283 (1976)
Scheinerman, E.R., West, D.B.: The interval number of a planar graph: Three intervals suffice. J. Comb. Theory Ser. B 35(3), 224–239 (1983)
Spinrad, J.P.: Efficient Graph Representations. Fields Institute Monographs, vol. 19. AMS (2003)
Tardos, G.: Transversals of 2-intervals, a topological approach. Combinatorica 15(1), 123–134 (1995)
Trotter, W.T., Harary, F.: On double and multiple interval graphs. J. Graph Theor. 3(3), 205–2011 (1979)
Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505–517 (1977)
Vialette, S.: On the computational complexity of 2-interval pattern matching problems. Theor. Comput. Sci. 312(2-3), 224–239 (2004)
Vialette, S.: Two-interval pattern problems. In: Encyclopedia of Algorithms. Springer (2008)
West, D.B.: A short proof of the degree bound for interval number. Discrete Math. 73(3), 309–310 (1989)
West, D.B., Shmoys, D.B.: Recognizing graphs with fixed interval number is NP-complete. Discrete Appl. Math. 8, 295–305 (1984)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fomin, F.V. et al. (2012). k-Gap Interval Graphs. In: Fernández-Baca, D. (eds) LATIN 2012: Theoretical Informatics. LATIN 2012. Lecture Notes in Computer Science, vol 7256. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29344-3_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-29344-3_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29343-6
Online ISBN: 978-3-642-29344-3
eBook Packages: Computer ScienceComputer Science (R0)