Abstract
The embedding problem is to decide, given an ordered pair of structures, whether or not there is an injective homomorphism from the first structure to the second. We study this problem using an established perspective in parameterized complexity theory: the universe size of the first structure is taken to be the parameter, and we define the embedding problem relative to a class \({\mathcal {A}}\) of structures to be the restricted version of the general problem where the first structure must come from \({\mathcal {A}}\). We initiate a systematic complexity study of this problem family, by considering classes whose structures are what we call rooted path structures; these structures have paths as Gaifman graphs. Our main theorem is a dichotomy theorem on classes of rooted path structures.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844–856 (1995)
Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: Advice classes of parameterized tractability. Ann. Pure Appl. Logic 84(1), 119–138 (1997)
Chen, H., Müller, M.: The fine classification of conjunctive queries and parameterized logarithmic space. Trans. Comput. Theory 7(2) (2015). Article No. 7
Chen, Y., Müller, M.: Bounded variable logic, parameterized logarithmic space, and Savitch’ theorem. In: Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, 2014. Proceedings, Part I, pp 183-195 (2014)
Elberfeld, M., Stockhusen, C., Tantau, T.: On the space and circuit complexity of parameterized problems: Classes and completeness. Algorithmica 71 (3), 661–701 (2015)
Flum, J., Grohe, M.: Describing parameterized complexity classes. Inf. Comput. 187(2), 291–319 (2003)
Flum, J., Grohe, M.: Parameterized complexity theory. Springer (2006)
Lin, B.: The parameterized complexity of k-biclique. In: Proceedings of the Twenty-Sixth Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2015, pp 605-615, CA, USA (2015)
Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4) (2008). Article No. 17
Acknowledgments
We thank the anonymous referees for their careful reading of the manuscript. Following their suggestions we added a number of examples, comments and discussions. The first author was supported by the Spanish Project MINECO COMMAS TIN2013-46181-C2-R, Basque Project GIU15/30, and Basque Grant UFI11/45. The authors wish to thank Eric Allender, Yijia Chen, and Michael Elberfeld for useful comments and discussion.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chen, H., Müller, M. The Parameterized Space Complexity of Embedding Along a Path. Theory Comput Syst 61, 851–870 (2017). https://doi.org/10.1007/s00224-016-9728-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-016-9728-7