Improved Lower Bounds for Graph Embedding Problems

In this paper, we give new, tight subexponential lower bounds for a number of graph embedding problems. We introduce two related combinatorial problems, which we call String Crafting and Orthogonal Vector crafting, and show that these cannot be solved in time \(2^{o(|s|/\log {|s|})}\), unless the Exponential Time Hypothesis fails.