Abstract
A homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H). Let H be a fixed graph with possible loops. In the list homomorphism problem, denoted by LHom(H), the instance is a graph G, whose every vertex is equipped with a subset of V(H), called list. We ask if there exists a homomorphism from G to H, such that every vertex from G is mapped to a vertex from its list.
We study the complexity of the LHom(H) problem in intersection graphs of various geometric objects. In particular, we are interested in answering the question for what graphs H and for what types of geometric objects, the LHom(H) problem can be solved in time subexponential in the number of vertices of the instance.
We fully resolve this question for string graphs, i.e., intersection graphs of continuous curves in the plane. Quite surprisingly, it turns out that the dichotomy coincides with the analogous dichotomy for graphs excluding a fixed path as an induced subgraph [Okrasa, Rzążewski, STACS 2021].
Then we turn our attention to intersections of fat objects. We observe that the (non) existence of subexponential-time algorithms in such classes is closely related to the size \(\textrm{mrc}(H)\) of a maximum reflexive clique in H, i.e., maximum number of pairwise adjacent vertices, each of which has a loop. We study the maximum value of \(\textrm{mrc}(H)\) that guarantees the existence of a subexponential-time algorithm for LHom(H) in intersection graphs of (i) convex fat objects, (ii) fat similarly-sized objects, and (iii) disks. In the first two cases we obtain optimal results, by giving matching algorithms and lower bounds.
Karolina Okrasa–Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant Agreement no. 714704.
Paweł Rzążewski–Supported by Polish National Science Centre grant no. 2018/31/D/ST6/00062.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Proofs of statements marked with (\(\spadesuit \)) can be found in the full version of the paper [19].
References
Alber, J., Fiala, J.: Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithms 52(2), 134–151 (2004). https://doi.org/10.1016/j.jalgor.2003.10.001
de Berg, M., Bodlaender, H.L., Kisfaludi-Bak, S., Marx, D., van der Zanden, T.C.: A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs. SIAM J. Comput. 49(6), 1291–1331 (2020). https://doi.org/10.1137/20M1320870
de Berg, M., Kisfaludi-Bak, S., Monemizadeh, M., Theocharous, L.: Clique-based separators for geometric intersection graphs. In: 32nd International Symposium on Algorithms and Computation, ISAAC 2021. LIPIcs, vol. 212, pp. 22:1–22:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPIcs.ISAAC.2021.22
Biró, C., Bonnet, É., Marx, D., Miltzow, T., Rzążewski, P.: Fine-grained complexity of coloring unit disks and balls. J. Comput. Geom. 9(2), 47–80 (2018). https://doi.org/10.20382/jocg.v9i2a4
Bonamy, M., et al.: EPTAS and subexponential algorithm for maximum clique on disk and unit ball graphs. J. ACM 68(2), 9:1-9:38 (2021). https://doi.org/10.1145/3433160
Bonnet, É., Rzążewski, P.: Optimality program in segment and string graphs. Algorithmica 81(7), 3047–3073 (2019). https://doi.org/10.1007/s00453-019-00568-7
Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discret. Math. 86(1–3), 165–177 (1990). https://doi.org/10.1016/0012-365X(90)90358-O
Edwards, K.: The complexity of colouring problems on dense graphs. Theor. Comput. Sci. 43, 337–343 (1986). https://doi.org/10.1016/0304-3975(86)90184-2
Fishkin, A.V.: Disk graphs: a short survey. In: Solis-Oba, R., Jansen, K. (eds.) WAOA 2003. LNCS, vol. 2909, pp. 260–264. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24592-6_23
Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S., Zehavi, M.: Finding, hitting and packing cycles in subexponential time on unit disk graphs. Discrete Computat. Geom. 62(4), 879–911 (2019). https://doi.org/10.1007/s00454-018-00054-x
Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S., Zehavi, M.: ETH-tight algorithms for long path and cycle on unit disk graphs. In: Cabello, S., Chen, D.Z. (eds.) 36th International Symposium on Computational Geometry, SoCG 2020, 23–26 June 2020, Zürich, Switzerland. LIPIcs, vol. 164, pp. 44:1–44:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). https://doi.org/10.4230/LIPIcs.SoCG.2020.44
Fomin, F.V., Lokshtanov, D., Saurabh, S.: Bidimensionality and geometric graphs. In: Rabani, Y. (ed.) Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 17–19 January 2012, pp. 1563–1575. SIAM (2012). https://doi.org/10.1137/1.9781611973099
Golumbic, M.C.: Chapter 8 - interval graphs. In: Golumbic, M.C. (ed.) Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol. 57, pp. 171–202. Elsevier (2004). https://doi.org/10.1016/S0167-5060(04)80056-6
Huson, M., Sen, A.: Broadcast scheduling algorithms for radio networks. In: Proceedings of MILCOM 1995, vol. 2, pp. 647–651 (1995). https://doi.org/10.1109/MILCOM.1995.483546
Impagliazzo, R., Paturi, R.: On the complexity of \(k\)-SAT. J. Comput. Syst. Sci. 62(2), 367–375 (2001). https://doi.org/10.1006/jcss.2000.1727
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001). https://doi.org/10.1006/jcss.2001.1774
Jungck, J.R., Viswanathan, R.: Chapter 1 - graph theory for systems biology: interval graphs, motifs, and pattern recognition. In: Robeva, R.S. (ed.) Algebraic and Discrete Mathematical Methods for Modern Biology, pp. 1–27. Academic Press, Boston (2015). https://doi.org/10.1016/B978-0-12-801213-0.00001-0
Kaufmann, M., Kratochvíl, J., Lehmann, K.A., Subramanian, A.R.: Max-tolerance graphs as intersection graphs: cliques, cycles, and recognition. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, 22–26 January 2006, pp. 832–841. ACM Press (2006). http://dl.acm.org/citation.cfm?id=1109557.1109649
Kisfaludi-Bak, S., Okrasa, K., Rzążewski, P.: Computing list homomorphisms in geometric intersection graphs. CoRR abs/2202.08896 (2022). https://arxiv.org/abs/2202.08896
Kisfaludi-Bak, S., van der Zanden, T.C.: On the exact complexity of Hamiltonian cycle and q-colouring in disk graphs. In: Fotakis, D., Pagourtzis, A., Paschos, V.T. (eds.) CIAC 2017. LNCS, vol. 10236, pp. 369–380. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57586-5_31
Kratochvíl, J., Matoušek, J.: Intersection graphs of segments. J. Comb. Theory Ser. B 62(2), 289–315 (1994). https://doi.org/10.1006/jctb.1994.1071
Kratochvíl, J.: String graphs. I. The number of critical nonstring graphs is infinite. J. Comb. Theory Ser. B 52(1), 53–66 (1991). https://doi.org/10.1016/0095-8956(91)90090-7
Kratochvíl, J.: String graphs. II. Recognizing string graphs is NP-hard. J. Comb. Theory Ser. B 52(1), 67–78 (1991). https://doi.org/10.1016/0095-8956(91)90091-W
Lekkeikerker, C., Boland, J.: Representation of a finite graph by a set of intervals on the real line. Fundam. Math. 51(1), 45–64 (1962). http://eudml.org/doc/213681
Marx, D.: Efficient approximation schemes for geometric problems? In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 448–459. Springer, Heidelberg (2005). https://doi.org/10.1007/11561071_41
Marx, D.: On the optimality of planar and geometric approximation schemes. In: FOCS 2007 Proceedings, pp. 338–348 (2007). https://doi.org/10.1109/FOCS.2007.50
Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using voronoi diagrams. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 865–877. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48350-3_72
Miller, G.L., Teng, S., Thurston, W.P., Vavasis, S.A.: Separators for sphere-packings and nearest neighbor graphs. J. ACM 44(1), 1–29 (1997). https://doi.org/10.1145/256292.256294
Okrasa, K., Rzążewski, P.: Subexponential algorithms for variants of the homomorphism problem in string graphs. J. Comput. Syst. Sci. 109, 126–144 (2020). https://doi.org/10.1016/j.jcss.2019.12.004
Smith, W.D., Wormald, N.C.: Geometric separator theorems and applications. In: FOCS 1998 Proceedings, pp. 232–243. IEEE Computer Society, Washington, DC, USA (1998)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Kisfaludi-Bak, S., Okrasa, K., Rzążewski, P. (2022). Computing List Homomorphisms in Geometric Intersection Graphs. In: Bekos, M.A., Kaufmann, M. (eds) Graph-Theoretic Concepts in Computer Science. WG 2022. Lecture Notes in Computer Science, vol 13453. Springer, Cham. https://doi.org/10.1007/978-3-031-15914-5_23
Download citation
DOI: https://doi.org/10.1007/978-3-031-15914-5_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-15913-8
Online ISBN: 978-3-031-15914-5
eBook Packages: Computer ScienceComputer Science (R0)