Tree-Depth and the Formula Complexity of Subgraph Isomorphism

DOI10.1137/20M1372925MaRDI QIDQ5885602zbMATH OpenFDO

Authors Deepanshu Kush, Benjamin Rossman

Publication date 4 April 2023

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.13302

zbMATH Keywords

circuit complexitysubgraph isomorphismtree-width

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
• Beating treewidth for average-case subgraph isomorphism
• scientific article; zbMATH DE number 7650232
• Logical complexity of induced subgraph isomorphism for certain families of graphs
• Lower bounds for subgraph isomorphism

Cites work

• \(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits
• A polynomial excluded-minor approximation of treedepth
• Beating treewidth for average-case subgraph isomorphism
• Can you beat treewidth?
• Formulas versus Circuits for Small Distance Connectivity
• Homomorphism preservation theorems
• scientific article; zbMATH DE number 6829287 (Why is no real title available?)
• scientific article; zbMATH DE number 6866317 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Improved bounds for the excluded-minor approximation of treedepth
• Lower bounds for subgraph isomorphism
• On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
• The set cover conjecture and subgraph isomorphism with a tree pattern
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• Towards tight(er) bounds for the excluded grid theorem
• Tree-depth, subgraph coloring and homomorphism bounds

Cited in

(7)

• Branch-depth: generalizing tree-depth of graphs
• On the Complexity of Extracting Subtree with Keeping Distinguishability
• scientific article; zbMATH DE number 1335884 (Why is no real title available?)
• Monotone arithmetic complexity of graph homomorphism polynomials
• Tree-depth and the Formula Complexity of Subgraph Isomorphism
• Closure property of contraction-depth of matroids
• Equi-rank homomorphism preservation theorem on finite structures

This page was built for publication: Tree-Depth and the Formula Complexity of Subgraph Isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5885602)