From Complexity Zoo
Revision as of 07:31, 14 May 2019 by Timeroot (talk | contribs) (starting table of graph substructures)
Jump to navigation Jump to search

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
GI-Complete O(1)
2 2 4 6
3 3 6 9
4 4 8 12
5 5 10 15