User:Timeroot - Revision history

Timeroot at 17:48, 12 June 2020

2020-06-12T17:48:15Z

Timeroot at 22:12, 14 May 2019

2019-05-14T22:12:43Z

Timeroot at 21:41, 14 May 2019

2019-05-14T21:41:28Z

Timeroot: continuing table

2019-05-14T20:03:50Z

continuing table

Timeroot: starting table of graph substructures

2019-05-14T07:31:44Z

starting table of graph substructures

Timeroot: Created page with "Real name: Alex Meiburg. Physics PhD student at UCSB."

2019-04-29T20:17:40Z

Created page with "Real name: Alex Meiburg. Physics PhD student at UCSB."

New page

Real name: Alex Meiburg.

Physics PhD student at UCSB.

← Older revision		Revision as of 17:48, 12 June 2020
Line 107:		Line 107:

	[3] For large G, only the vertices of degree at least 3 need to be compared. The rest is simply comparing induced path lengths. See "Containment relations in split graphs" by Petr A.Golovach et al.		[3] For large G, only the vertices of degree at least 3 need to be compared. The rest is simply comparing induced path lengths. See "Containment relations in split graphs" by Petr A.Golovach et al.
		+
		+	==Quantum classes==
		+	Some notes on different error/proof types of quantum classes.
		+
		+	P: Can solve directly, [0], [1]
		+	NP: Given classical proof, [0], [1]
		+	MA: Given classical proof, [0,1/3], [1]
		+
		+	EQP: Solving on QTM, [0], [1]
		+	BQP: Solving on QTM, [0,1/3], [2/3,1]
		+	RQP: Solving on QTM, [0], [2/3,1]
		+	BQP1: Solving on QTM, [0,1/3], [1]
		+
		+	Note: BQP1 = coRQP
		+
		+	QCMA: Given classical proof, [0,1/3], [2/3,1]
		+	QCMA1: Given classical proof, [0,1/3], [1]
		+
		+	NQP: Solving directly, [0], [epsilon,1]. Compare with: NP: Directly, [0],[1].
		+
		+	QMA: Given quantum proof, [0,1/3], [2/3,1]
		+	QMA1: Given quautm proof, [0,1/3], [1]
		+
		+
		+	Could define EQMA and EQCMA as "If it's YES, then there's an input that leads to YES with prob 1,
		+	otherwise any input leads to NO with prob 1." Hard to imagine how these would arise naturally, though.

@@ Line 66: / Line 66: @@
 | ...complicated...
 |-
-|| '''Homeomorphism'''
+|| '''Homomorphism'''
+| Vertex identification, multiedge simplification<br />vertex addition, edge addition
 |-
-|| '''Full Homeomorphism'''
+|| '''Homomorphic Equivalence'''
+| Homo both ways
 |-
-|| '''Surjective Homeomorphism'''
+|| '''Full Homomorphism'''
+| Homo: Edge preserving + non-edge preserving
 |-
 |}

@@ Line 14: / Line 14: @@
 Complexities are usually given in the form of {complete class; upper bound on runtime; lower bound on runtime under reasonable assumptions}. I assume the ETH (that 3SAT can't be solved in 2^o(n)), which has the FPT corollary Clique can't be solved in f(k)n<sup>o(k)</sup>. If there a simple case that shows why something is NP-Hard, then I will mention it: in particular, finding Hamiltonian cycles and cliques are hard.
-{| class="wikitable" style="text-align: center; width: 1000px; height: 200px;"
+{| class="wikitable" style="text-align: center;"
 |+ Graph Substructure Table
 |-
@@ Line 24: / Line 24: @@
 ! scope="col" | Complexity (fixed H)
 |-
-! scope="row" | Graph Isomorphism
+|| '''Graph Isomorphism'''
 | ''None'' || '''E'''(u,v) ↔ '''E'''(''f''(u), ''f''(v))<br />''f''<sub>V</sub> bijective || Equivalence <br />Not WQO (e.g. Kn)<br />DCC, ACC || GI-Complete <br /> e<sup>O(log<sup>3</sup> G)</sup> ''[1]'' <br /> - || ''Trivial'' <br /> (Fixed vertex count; ACC)
 |-
-! scope="row" | Induced Subgraph
+|| '''Induced Subgraph'''
 | Vertex deletion || '''E'''(u,v) ↔ '''E'''(''f''(u), ''f''(v))<br />''f''<sub>V</sub> injective || Not WQO (e.g. Cn)<br />DCC || NP-Complete (cliques) <br /> G<sup>H+2</sup> <br /> 2<sup>o(G)</sup> || W[1]-Complete (cliques) <br /> G<sup>H+2</sup> <br /> f(H)G<sup>o(H)</sup>
 |-
-! scope="row" | Subgraph
+|| '''Subgraph'''
 | Vertex deletion, Edge deletion || '''E'''(u,v)  → '''E'''(''f''(u), ''f''(v))<br />''f''<sub>V</sub> injective || Not WQO (e.g. Cn)<br />DCC || NP-Complete (cliques) <br /> G<sup>H+2</sup> <br /> 2<sup>o(G)</sup> || W[1]-Complete (cliques) <br /> G<sup>H+2</sup> <br /> f(H)G<sup>o(H)</sup>
 |-
-! scope="row" | Spanning Subgraph
+|| '''Spanning Subgraph'''
 | Edge deletion || '''E'''(u,v)  → '''E'''(''f''(u), ''f''(v))<br />''f''<sub>V</sub> bijective || Not WQO (e.g. Cn)<br />DCC, ACC || NP-Complete (Hamiltonian cycle) <br /> G<sup>H+2</sup> <br /> 2<sup>o(G)</sup> || ''Trivial'' <br />(Fixed vertex count; ACC)
 |-
-! scope="row" | Dissolution <br />Equivalent to to ''Smoothing''<br />Dual to ''Subdivision'' or ''Expansion''<br />
+|| '''Dissolution''' <br />Dual to '''Subdivision'''
-| Edge deletion || ''f''<sub>V</sub> injective<br />''f''<sub>E</sub> carries edges to distinct induced paths || Not WQO (e.g. Kn)<br />DCC || NP-Complete ''[2]'' <br /> G<sup>H+2</sup> <br /> 2<sup>o(G)</sup> || -
+| Vertex Dissolution || ''f''<sub>V</sub> injective<br />''f''<sub>E</sub> carries edges to distinct induced paths || Not WQO (e.g. Kn)<br />DCC || NP-Complete ''[2]'' <br /> G<sup>H+2</sup> <br /> 2<sup>o(G)</sup> || FPT<br />H<sup>H</sup>G<br />2<sup>o(H)</sup>G ''[3]''
 |}
 References:
 [1] https://cstheory.stackexchange.com/a/40373/12211
-[2] Own work

@@ Line 8: / Line 8: @@
 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.
+Being well-quasi-ordered (WQO) 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. A weaker property than being WQO is the descending chain condition (DCC), which means that there are no infinite chains of containment. Properties that respect some integral measure of size (e.g. |V| or |E|) always have the DCC, but others such as graph homomorphism might not. When a property is not WQO, I will usually provide an example of why, such as the cliques Kn, cycles Cn, or bipartite graphs Knn, that form an infinite antichain. Finally, there is also an Ascending Chain Condition (ACC), which usually applies when the vertex or edge count is fixed: all edges containing a given H are of a maximum size.
-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.
+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. This includes all with the ascending chain condition, as there are just finitely many G's to check for.
 {| class="wikitable" style="text-align: center; width: 1000px; height: 200px;"
@@ Line 17: / Line 19: @@
 ! scope="col" | Name
 ! scope="col" | Reductions
-! scope="col" | Map ''f'': G → H
+! scope="col" | Map ''f'': H → G
 ! scope="col" | Ordering Properties
 ! scope="col" | Complexity (varying H)
@@ Line 23: / Line 25: @@
 |-
 ! scope="row" | Graph Isomorphism
-| ''None'' || '''E'''(''f''(u), ''f''(v))  ↔ '''E'''(u,v)<br />''f'' bijective || Equivalence <br />Not WQO || GI-Complete || O(1)
+| ''None'' || '''E'''(u,v) ↔ '''E'''(''f''(u), ''f''(v))<br />''f''<sub>V</sub> bijective || Equivalence <br />Not WQO (e.g. Kn)<br />DCC, ACC || GI-Complete <br /> e<sup>O(log<sup>3</sup> G)</sup> ''[1]'' <br /> - || ''Trivial'' <br /> (Fixed vertex count; ACC)
 |-
-! scope="row" | 2
+! scope="row" | Induced Subgraph
-| 2 || 4 || 6
+| Vertex deletion || '''E'''(u,v) ↔ '''E'''(''f''(u), ''f''(v))<br />''f''<sub>V</sub> injective || Not WQO (e.g. Cn)<br />DCC || NP-Complete (cliques) <br /> G<sup>H+2</sup> <br /> 2<sup>o(G)</sup> || W[1]-Complete (cliques) <br /> G<sup>H+2</sup> <br /> f(H)G<sup>o(H)</sup>
 |-
-! scope="row" | 3
+! scope="row" | Subgraph
-| 3 || 6 || 9
+| Vertex deletion, Edge deletion || '''E'''(u,v)  → '''E'''(''f''(u), ''f''(v))<br />''f''<sub>V</sub> injective || Not WQO (e.g. Cn)<br />DCC || NP-Complete (cliques) <br /> G<sup>H+2</sup> <br /> 2<sup>o(G)</sup> || W[1]-Complete (cliques) <br /> G<sup>H+2</sup> <br /> f(H)G<sup>o(H)</sup>
 |-
-! scope="row" | 4
+! scope="row" | Spanning Subgraph
-| 4 || 8 || 12
+| Edge deletion || '''E'''(u,v)  → '''E'''(''f''(u), ''f''(v))<br />''f''<sub>V</sub> bijective || Not WQO (e.g. Cn)<br />DCC, ACC || NP-Complete (Hamiltonian cycle) <br /> G<sup>H+2</sup> <br /> 2<sup>o(G)</sup> || ''Trivial'' <br />(Fixed vertex count; ACC)
 |-
-! scope="row" | 5
+! scope="row" | Dissolution <br />Equivalent to to ''Smoothing''<br />Dual to ''Subdivision'' or ''Expansion''<br />
-| 5 || 10 || 15
+| Edge deletion || ''f''<sub>V</sub> injective<br />''f''<sub>E</sub> carries edges to distinct induced paths || Not WQO (e.g. Kn)<br />DCC || NP-Complete ''[2]'' <br /> G<sup>H+2</sup> <br /> 2<sup>o(G)</sup> || -
 |}

← Older revision		Revision as of 07:31, 14 May 2019
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
		+	\|}