Difference between revisions of "User:Timeroot"
(Created page with "Real name: Alex Meiburg. Physics PhD student at UCSB.") |
(starting table of graph substructures) |
||
Line 1: | Line 1: | ||
Real name: Alex Meiburg. | Real name: Alex Meiburg. | ||
− | Physics PhD student at UCSB. | + | 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. | ||
+ | |||
+ | {| class="wikitable" style="text-align: center; width: 1000px; height: 200px;" | ||
+ | |+ Graph Substructure Table | ||
+ | |- | ||
+ | ! scope="col" | Name | ||
+ | ! scope="col" | Reductions | ||
+ | ! scope="col" | Map ''f'': G → H | ||
+ | ! scope="col" | Ordering Properties | ||
+ | ! scope="col" | Complexity (varying H) | ||
+ | ! scope="col" | Complexity (fixed H) | ||
+ | |- | ||
+ | ! scope="row" | Graph Isomorphism | ||
+ | | ''None'' || '''E'''(''f''(u), ''f''(v)) ↔ '''E'''(u,v)<br />''f'' bijective || Equivalence <br />Not WQO || GI-Complete || O(1) | ||
+ | |- | ||
+ | ! scope="row" | 2 | ||
+ | | 2 || 4 || 6 | ||
+ | |- | ||
+ | ! scope="row" | 3 | ||
+ | | 3 || 6 || 9 | ||
+ | |- | ||
+ | ! scope="row" | 4 | ||
+ | | 4 || 8 || 12 | ||
+ | |- | ||
+ | ! scope="row" | 5 | ||
+ | | 5 || 10 || 15 | ||
+ | |} |
Revision as of 07:31, 14 May 2019
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 |