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

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

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

• 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 7559154 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• 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
• Improved bounds for the excluded-minor approximation of treedepth
• Lower bounds for subgraph isomorphism
• On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• Towards tight(er) bounds for the excluded grid theorem
• Tree-depth, subgraph coloring and homomorphism bounds
• \(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits

Cited in

(5)

• Tree-depth and the Formula Complexity of Subgraph Isomorphism
• 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
• Branch-depth: generalizing tree-depth of graphs

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)