User:Timeroot
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) f bijective |
Equivalence Not WQO |
GI-Complete | O(1) |
| 2 | 2 | 4 | 6 | ||
| 3 | 3 | 6 | 9 | ||
| 4 | 4 | 8 | 12 | ||
| 5 | 5 | 10 | 15 |