Tree-Depth and the Formula Complexity of Subgraph Isomorphism

DOI10.1137/20M1372925MaRDI QIDQ5885602

Benjamin Rossman, Deepanshu Kush

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)

Related Items (1)

Monotone arithmetic complexity of graph homomorphism polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits
• Beating treewidth for average-case subgraph isomorphism
• Tree-depth, subgraph coloring and homomorphism bounds
• Homomorphism preservation theorems
• Formulas versus Circuits for Small Distance Connectivity
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• Improved Bounds for the Excluded-Minor Approximation of Treedepth
• LOWER BOUNDS FOR SUBGRAPH ISOMORPHISM
• Towards Tight(er) Bounds for the Excluded Grid Theorem
• On the $AC^0$ Complexity of Subgraph Isomorphism

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