The parameterized space complexity of embedding along a path

DOI10.1007/S00224-016-9728-7MaRDI QIDQ2408562zbMATH OpenOpenAlexFDO

Authors Hubie Chen, Moritz Müller

Publication date 12 October 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.09022

zbMATH Keywords

embeddinghomomorphismparameterized space complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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 $clA$ of structures to be the restricted version of the general problem where the first structure must come from $clA$. 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.

Recommendations

• The hardness of embedding grids and walls
• Understanding the Complexity of Induced Subgraph Isomorphisms
• A slice theoretic approach for embedding problems on digraphs
• The parametric ordinal-recursive complexity of Post embedding problems
• The computable embedding problem

Cites work

• Advice classes of parametrized tractability
• Bounded variable logic, parameterized logarithmic space, and Savitch's theorem
• Color-coding
• Describing parameterized complexity classes
• On the space and circuit complexity of parameterized problems: classes and completeness
• Parametrized complexity theory.
• The fine classification of conjunctive queries and parameterized logarithmic space
• The parameterized complexity of \(k\)-biclique
• Undirected connectivity in log-space

Cited in

(2)

• The hardness of embedding grids and walls
• A practical algorithm for structure embedding

This page was built for publication: The parameterized space complexity of embedding along a path

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2408562)