Real name: Alex Meiburg.
Physics PhD student at UCSB (expected grad ~2024).
I'm trying to compile information on types of graph containment. Complexity bounds should have upper- and lower-bounds on difficulty with fixed H and varying H.
For instance, for many types of substructure (such as subgraph), finding an H inside G can be trivially done in O(G^H) time. (I use the name, G, synonymously with |V(G)|, its vertex size.) Worst case, this is exponential with H. But if you fix H, then there may (or may not) be algorithms that 'move' the difficulty, e.g. O(H! * G^2). This would then by fixed-parameter tractable.
Being WQO (well-quasi-ordered) is important, because it implies that any property closed under these operations can be described by a forbidden substructure. The classic case is minors, which are a WQO and can have substructure found in O(G^2) time with a fixed H. There is a very nontrivial constant factor that depends on H, though, rendering most of these algorithms impractical. I'll use the notation RS(H) to indicate that an algorithm uses the Robertson-Seymour subroutine, and so although might have fixed H dependence, the constant matters.
For relations that requires G and H are of the same size in some sense (such as Graph Isomorphism, Spanning Subgraph, Subdivision etc. -- technically, those that with fixed H admit a kernelization algorithm), the "fixed H" problem becomes trivial.
|Name||Reductions||Map f: G → H||Ordering Properties||Complexity (varying H)||Complexity (fixed H)|
|Graph Isomorphism||None||E(f(u), f(v)) ↔ E(u,v)