research-article

Public Access

Tight Lower Bounds on Graph Embedding Problems

Authors:

Fedor V. Fomin,

Alexander Golovnev,

Alexander S. Kulikov,

Jakub Pachocki,

Arkadiusz SocałaAuthors Info & Claims

Journal of the ACM (JACM), Volume 64, Issue 3

Article No.: 18, Pages 1 - 22

https://doi.org/10.1145/3051094

Published: 16 June 2017 Publication History

Abstract

We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph G to graph H cannot be done in time |V(H)|^o(|V(G)|). We also show an exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of |V(H)|^o(|V(H)|)-time algorithm deciding if graph G is a subgraph of H. For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems.

Moreover, as a consequence of our reductions, conditional lower bounds follow for other related problems such as Locally Injective Homomorphism, Graph Minors, Topological Graph Minors, Minimum Distortion Embedding and Quadratic Assignment Problem.

References

[1]

Omid Amini, Fedor V. Fomin, and Saket Saurabh. 2012. Counting subgraphs via homomorphisms. SIAM J. Discr. Math. 26, 2 (2012), 695--717.

[2]

Per Austrin. 2010. Towards sharp inapproximability for any 2-CSP. SIAM J. Comput. 39, 6 (2010), 2430--2463.

Digital Library

[3]

Mihai Bădoiu, Julia Chuzhoy, Piotr Indyk, and Anastasios Sidiropoulos. 2005a. Low-distortion embeddings of general metrics into the line. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC’05). ACM, 225--233.

Digital Library

[4]

Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, and Anastasios Sidiropoulos. 2005b. Approximation algorithms for low-distortion embeddings into low-dimensional spaces. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’05). SIAM, 119--128.

Digital Library

[5]

Libor Barto, Marcin Kozik, and Todd Niven. 2008. Graphs, polymorphisms and the complexity of homomorphism problems. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC’08). 789--796.

Digital Library

[6]

Richard Beigel and David Eppstein. 2005. 3-coloring in time O(1.3289<sup>n</sup>). J. Algor. 54, 2 (2005), 444--453.

Digital Library

[7]

Andreas Björklund. 2014. Determinant sums for undirected hamiltonicity. SIAM J. Comput. 43, 1 (2014), 280--299.

Digital Library

[8]

Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. 2009. Set partitioning via inclusion--exclusion. SIAM J. Comput. 39, 2 (2009), 546--563.

Digital Library

[9]

Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, and Johan M. M. van Rooij. 2012. Fast algorithms for max independent set. Algorithmica 62, 1--2 (2012), 382--415.

Digital Library

[10]

Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. 2006. Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72, 8 (2006), 1346--1367.

Digital Library

[11]

Marek Cygan, Fedor Fomin, Bart M. P. Jansen, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. 2014. School on Parameterized Algorithms and Complexity—Open Problems. Retrieved from http://fptschool.mimuw.edu.pl/opl.pdf.

[12]

Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Dániel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer.

Digital Library

[13]

Marek Cygan and Marcin Pilipczuk. 2012. Bandwidth and distortion revisited. Discr. Appl. Math. 160, 4--5 (2012), 494--504.

[14]

Tomás Feder and Moshe Y. Vardi. 1998. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput. 28, 1 (1998), 57--104.

Digital Library

[15]

Uriel Feige. 2000. Coping with the NP-hardness of the graph bandwidth problem. In Proceedings of the 7th Scandinavian Workshop on Algorithm Theory (SWAT’00). Lecture Notes in Computer Science, Vol. 1851. Springer, Berlin, 10--19.

Digital Library

[16]

Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances A. Rosamond, and Saket Saurabh. 2013. Distortion is fixed parameter tractable. ACM Trans. Comput. Theory 5, 4 (2013), 16.

Digital Library

[17]

Jirí Fiala, Petr A. Golovach, and Jan Kratochvíl. 2008. Computational complexity of the distance constrained labeling problem for trees (extended abstract). In Proceedings of the 35th International Colloquium of Automata, Languages and Programming (ICALP’08). Lecture Notes in Computer Science, Vol. 5125. Springer, 294--305.

Digital Library

[18]

Jirí Fiala and Jan Kratochvíl. 2008. Locally constrained graph homomorphisms - structure, complexity, and applications. Comput. Sci. Rev. 2, 2 (2008), 97--111.

Digital Library

[19]

Fedor Fomin, Kazuo Iwama, and Dieter Kratsch. 2008. Moderately exponential time algorithms (dagstuhl seminar 08431). In Dagstuhl Reports. Retrieved from http://drops.dagstuhl.de/opus/volltexte/2008/1798/pdf/08431.SWM.Paper.1798.pdf. 1.

[20]

Fedor V. Fomin, Pinar Heggernes, and Dieter Kratsch. 2007. Exact algorithms for graph homomorphisms. Theor. Comput. Syst. 41, 2 (2007), 381--393.

Digital Library

[21]

Fedor V. Fomin and Dieter Kratsch. 2010. Exact Exponential Algorithms. Springer.

Digital Library

[22]

Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. 2011. An exact algorithm for minimum distortion embedding. Theor. Comput. Sci. 412, 29 (2011), 3530--3536.

Digital Library

[23]

Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.

Digital Library

[24]

Jerrold R. Griggs and Roger K. Yeh. 1992. Labelling Graphs with a Condition at Distance 2. SIAM J. Discr. Math. 5, 4 (1992), 586--595.

Digital Library

[25]

Martin Grohe. 2007. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54, 1 (2007).

Digital Library

[26]

Frédéric Havet, Martin Klazar, Jan Kratochvíl, Dieter Kratsch, and Mathieu Liedloff. 2011. Exact algorithms for L(2, 1)-labeling of graphs. Algorithmica 59, 2 (2011), 169--194.

Digital Library

[27]

Michael Held and Richard M. Karp. 1962. A dynamic programming approach to sequencing problems. J. SIAM 10 (1962), 196--210.

[28]

Pavol Hell and Jaroslav Nešetřil. 1990. On the complexity of H-coloring. J. Combin. Theory Ser. B 48, 1 (1990), 92--110.

Digital Library

[29]

Pavol Hell and Jaroslav Nešetřil. 2004. Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and its Applications, Vol. 28. Oxford University Press, Oxford.

[30]

Thore Husfeldt, Ramamohan Paturi, Gregory B. Sorkin, and Ryan Williams. 2013. Exponential algorithms: Algorithms and complexity beyond polynomial time (dagstuhl seminar 13331). In Dagstuhl Reports. Retrieved from http://drops.dagstuhl.de/opus/volltexte/2013/4342/pdf/dagrep_v003_i008_p040_s13331.pdf. 63.

[31]

Russell Impagliazzo and Ramamohan Paturi. 2001. On the complexity of k-SAT. J. Comput. Syst. Sci. 62, 2 (2001), 367--375.

Digital Library

[32]

Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001a. Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 4 (2001), 512--530.

Digital Library

[33]

Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001b. Which problems have strongly exponential complexity. J. Comput. Syst. Sci. 63, 4 (2001), 512--530.

Digital Library

[34]

Konstanty Junosza-Szaniawski, Jan Kratochvíl, Mathieu Liedloff, Peter Rossmanith, and Paweł Rzażewski. 2013. Fast exact algorithm for L(2, 1)-labeling of graphs. Theor. Comput. Sci. 505 (2013), 42--54.

Digital Library

[35]

Claire Kenyon, Yuval Rabani, and Alistair Sinclair. 2009. Low distortion maps between point sets. SIAM J. Comput. 39, 4 (2009), 1617--1636.

Digital Library

[36]

Eugene L. Lawler. 1976. A note on the complexity of the chromatic number problem. Inf. Process. Lett. 5, 3 (1976), 66--67.

[37]

Andrzej Lingas and Martin Wahlen. 2009. An exact algorithm for subgraph homeomorphism. J. Discr. Algorithms 7, 4 (2009), 464--468.

Digital Library

[38]

Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. 2011. Lower bounds based on the exponential time hypothesis. Bull. EATCS 105 (2011), 41--72.

[39]

Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. 2013. Lower bounds based on the exponential time hypothesis. Bull. EATCS 3, 105 (2013).

[40]

László Lovász. 2012. Large Networks and Graph Limits. Vol. 60. American Mathematical Soc.

[41]

Dániel Marx. 2010. Can you beat treewidth? Theor. Comput. 6, 1 (2010), 85--112.

[42]

Dániel Marx and Michal Pilipczuk. 2014. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS’14). 542--553.

[43]

Prasad Raghavendra. 2008. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC’08). 245--254.

Digital Library

[44]

Neil Robertson and Paul D. Seymour. 1995. Graph minors. XIII. The disjoint paths problem. J. Combin. Theory Ser. B 63, 1 (1995), 65--110.

Digital Library

[45]

J. M. Robson. 1986. Algorithms for maximum independent sets. J. Algor. 7, 3 (1986), 425--440.

[46]

Paweł Rzażewski. 2014. Exact algorithm for graph homomorphism and locally injective graph homomorphism. Inf. Process. Lett. 114, 7 (2014), 387--391.

Digital Library

[47]

Michael Sipser. 2005. Introduction to the Theory of Computation. Cengage Learning.

[48]

Robert Endre Tarjan and Anthony E. Trojanowski. 1977. Finding a maximum independent set. SIAM J. Comput. 6, 3 (1977), 537--546.

Digital Library

[49]

Patrick Traxler. 2008. The time complexity of constraint satisfaction. In Parameterized and Exact Computation. Springer, 190--201.

Digital Library

[50]

Magnus Wahlström. 2010. Problem 5.21. time complexity of graph homomorphism. In Exact Complexity of NP-Hard Problems. Dagstuhl Seminar 10441 Final Report, Ramamohan Paturi Thore Husfeldt, Dieter Kratsch and Gregory Sorkin (Eds.). Dagstuhl.

[51]

Magnus Wahlström. 2011. New plain-exponential time classes for graph homomorphism. Theor. Comput. Syst. 49, 2 (2011), 273--282.

Digital Library

[52]

Gerhard J. Woeginger. 2003. Exact algorithms for NP-hard problems: A survey. In Combinatorial Optimization—Eureka, You Shrink&excl;Lecture Notes in Computer Science, Vol. 2570. Springer-Verlag, Berlin, 185--207.

Digital Library

Cited By

Robles MCavero SPardo ECordón O(2025)Multi-armed bandit for the cyclic minimum sitting arrangement problemComputers & Operations Research10.1016/j.cor.2025.107034(107034)Online publication date: Mar-2025
https://doi.org/10.1016/j.cor.2025.107034
Ganian RHamm TKorchemna VOkrasa KSimonov K(2024)The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-WidthACM Transactions on Algorithms10.1145/365251420:3(1-26)Online publication date: 25-Mar-2024
https://dl.acm.org/doi/10.1145/3652514
Björklund AKaski PMarx D(2021)The fine-grained complexity of computing the tutte polynomial of a linear matroidProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458203(2333-2345)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458203
Show More Cited By

Index Terms

Tight Lower Bounds on Graph Embedding Problems
1. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
    2. Parameterized complexity and exact algorithms

Recommendations

Tight Running Time Lower Bounds for Vertex Deletion Problems

For a graph class Π, the Π-Vertex Deletion problem has as input an undirected graph G = (V,E) and an integer k and asks whether there is a set of at most k vertices that can be deleted from G such that the resulting graph is a member of Π. By a classic ...
Tight Lower Bounds for the Complexity of Multicoloring

In the multicoloring problem, also known as (a:b)-coloring or b-fold coloring, we are given a graph G and a set of a colors, and the task is to assign a subset of b colors to each vertex of G so that adjacent vertices receive disjoint color subsets. ...
Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
Approximation and Online Algorithms
Abstract
Given a graph $G = (V, E)$ and a set $T = {(s_{i}, t_{i}) : 1 \leq i \leq k} \subseteq V \times V$ of k pairs, the k-Vertex-Disjoint-Paths (resp. k-Edge-Disjoint-Paths) problem asks to determine whether there exist k pairwise vertex-disjoint (resp. edge-disjoint) paths $P_{1}, P_{2}, \dots, P_{k}$ in G such ... $_{}$ $_{}$ $_{}$
$\frac{}{}$
$^{}$ $^{}$

Comments

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 64, Issue 3

June 2017

294 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3107927

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 June 2017

Accepted: 01 February 2017

Revised: 01 October 2016

Received: 01 February 2016

Published in JACM Volume 64, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Government of the Russian Federation
NSF
National Science Centre of Poland

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
625
Total Downloads

Downloads (Last 12 months)128
Downloads (Last 6 weeks)16

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Robles MCavero SPardo ECordón O(2025)Multi-armed bandit for the cyclic minimum sitting arrangement problemComputers & Operations Research10.1016/j.cor.2025.107034(107034)Online publication date: Mar-2025
https://doi.org/10.1016/j.cor.2025.107034
Ganian RHamm TKorchemna VOkrasa KSimonov K(2024)The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-WidthACM Transactions on Algorithms10.1145/365251420:3(1-26)Online publication date: 25-Mar-2024
https://dl.acm.org/doi/10.1145/3652514
Björklund AKaski PMarx D(2021)The fine-grained complexity of computing the tutte polynomial of a linear matroidProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458203(2333-2345)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458203
Fomin FLokshtanov DMihajlin ISaurabh SZehavi M(2021)Computation of Hadwiger Number and Related Contraction ProblemsACM Transactions on Computation Theory10.1145/344863913:2(1-25)Online publication date: 26-Mar-2021
https://dl.acm.org/doi/10.1145/3448639
Okrasa KRzaͅżewski P(2021)Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth GraphsSIAM Journal on Computing10.1137/20M132014650:2(487-508)Online publication date: 1-Apr-2021
https://doi.org/10.1137/20M1320146
Allair CVigneron A(2021)Pattern Matching in Doubling SpacesAlgorithms and Data Structures10.1007/978-3-030-83508-8_5(57-70)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-83508-8_5
Bodlaender HHanaka TKobayashi YKobayashi YOkamoto YOtachi Yvan der Zanden T(2020)Subgraph Isomorphism on Graph Classes that Exclude a SubstructureAlgorithmica10.1007/s00453-020-00737-z82:12(3566-3587)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s00453-020-00737-z
Agrawal ALokshtanov DSaurabh SZehavi M(2019)Split ContractionACM Transactions on Computation Theory10.1145/331990911:3(1-22)Online publication date: 31-May-2019
https://dl.acm.org/doi/10.1145/3319909
Bonamy MKowalik łPilipczuk MSocała AWrochna M(2019)Tight Lower Bounds for the Complexity of MulticoloringACM Transactions on Computation Theory10.1145/331390611:3(1-19)Online publication date: 2-Apr-2019
https://dl.acm.org/doi/10.1145/3313906
Bodlaender HHanaka TOkamoto YOtachi Yvan der Zanden T(2019)Subgraph Isomorphism on Graph Classes that Exclude a SubstructureAlgorithms and Complexity10.1007/978-3-030-17402-6_8(87-98)Online publication date: 27-May-2019
https://dl.acm.org/doi/10.1007/978-3-030-17402-6_8
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents