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.

Graph Substructure Table

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