Difference between revisions of "User:Timeroot"

From Complexity Zoo
Jump to navigation Jump to search
 
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.

Latest revision as of 17:48, 12 June 2020

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 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. This includes all with the ascending chain condition, as there are just finitely many G's to check for.

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)no(k). 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.

Graph Substructure Table
Name Reductions Map f: H → G Ordering Properties Complexity (varying H) Complexity (fixed H)
Graph Isomorphism None E(u,v) ↔ E(f(u), f(v))
fV bijective
Equivalence
Not WQO (e.g. Kn)
DCC, ACC
GI-Complete
eO(log3 G) [1]
-
Trivial
(Fixed vertex count; ACC)
Induced Subgraph Vertex deletion E(u,v) ↔ E(f(u), f(v))
fV injective
Not WQO (e.g. Cn)
DCC
NP-Complete (cliques)
GH+2
2o(G)
W[1]-Complete (cliques)
GH+2
f(H)Go(H)
Subgraph Vertex deletion, Edge deletion E(u,v) → E(f(u), f(v))
fV injective
Not WQO (e.g. Cn)
DCC
NP-Complete (cliques)
GH+2
2o(G)
W[1]-Complete (cliques)
GH+2
f(H)Go(H)
Spanning Subgraph Edge deletion E(u,v) → E(f(u), f(v))
fV bijective
Not WQO (e.g. Cn)
DCC, ACC
NP-Complete (Hamiltonian cycle)
GH+2
2o(G)
Trivial
(Fixed vertex count; ACC)
Dissolution
Dual to Subdivision
Vertex Dissolution fV injective
fE carries edges to distinct induced paths
Not WQO (e.g. Kn)
DCC
NP-Complete [2]
GH+2
2o(G)
FPT
HHG
2o(H)G [3]
Homeomorphism Dissolution, Subdivision
Induced Topological Minor Vertex deletion, smoothing
(Multiedge simplification?)
Topological Minor Vertex deletion, edge deletion, smoothing
Induced Minor Vertex deletion, contraction
(Multiedge simplification?)
Minor Vertex deletion, edge deletion, contraction
Induced Immersion Vertex deletion, lifting
(Multiedge simplification?)
Immersion Vertex deletion, edge deletion, lifting
Weak Immersion Vertex deletion, edge deletion, lifting, subdivision
(smoothing?)
Strong Immersion ...complicated...
Homomorphism Vertex identification, multiedge simplification
vertex addition, edge addition
Homomorphic Equivalence Homo both ways
Full Homomorphism Homo: Edge preserving + non-edge preserving
Surjective Homomorphism
aka Epimorphism
no vertex addition
Faithful Homomorphism https://math.stackexchange.com/questions/2704804/what-is-the-difference-between-a-full-and-a-faithful-graph-homomorphism
Injective Homomorphism
aka Monomorphism
Homo: Edge preserving + injective
same as subgraph, unless there are multiple edges
"Embedding" Homo: Edge preserving + injective + non-edge preserving
same as induced subgraph, unless there are multiple edges

Definition of operations:

  • Vertex deletion: Remove a vertex from the graph, and all edges using that vertex
  • Edge deletion: Remove an edge from a graph
  • Dissolution: Given a degree-2 vertex u with neighbors v and w, remove u and add an edge (v,w). u cannot have a loop. If v and w are neighbors, then this creates a multiedge. If multiple edges are allowed and v=w, then dissolution creates a loop at v. If loops aren't allowed and v=w then u cannot be dissolved. Also called Smoothing
  • Subdivision: Given an edge (v,w), remove that edge, create a new vertex u, and add edges (v,u) and (u,w). Also called Expansion. The opposite of dissolution.
  • Vertex identification: Given two distinct vertices u and v, delete v. For each edge (v,w) that was deleted, add a new edge (u,w). This may create multiedges.
  • Edge contraction: Vertex identification, restricted to the case where u and v are neighbors. No loop is created at u.
  • Lifting: If there is an edge (u,v) and another edge (v,w), then remove these two edges from the graph and add an edge (u,w). When combined with vertex deletion, includes dissolution.
  • Multiedge simplification: If there are multiple edges (u,v), then remove one of them. Special case of edge deletion.
  • Loop simplification: Remove a loop. Special case of edge deletion.

References:

[1] https://cstheory.stackexchange.com/a/40373/12211

[2] NP-Hardness was originally "observed" in "On the complexity of finding iso-and other morphisms for partial k-trees" by J. Matoušek, R. Thomas, although the reduction is somewhat nontrivial and doesn't seem to be written down anywhere.

[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.