Tree-Depth and the Formula Complexity of Subgraph Isomorphism

DOI10.1137/20M1372925MaRDI QIDQ5885602FDOQ5885602

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

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

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)

Cites Work

• Tree-depth, subgraph coloring and homomorphism bounds
• Can you beat treewidth?
• Title not available (Why is that?)
• Homomorphism preservation theorems
• \(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits
• Title not available (Why is that?)
• Lower bounds for subgraph isomorphism
• Towards tight(er) bounds for the excluded grid theorem
• Beating treewidth for average-case subgraph isomorphism
• On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• Formulas versus Circuits for Small Distance Connectivity
• A polynomial excluded-minor approximation of treedepth
• Title not available (Why is that?)
• Improved bounds for the excluded-minor approximation of treedepth
• Title not available (Why is that?)

Cited In (4)

• Branch-depth: generalizing tree-depth of graphs
• Monotone arithmetic complexity of graph homomorphism polynomials
• On the Complexity of Extracting Subtree with Keeping Distinguishability
• Title not available (Why is that?)

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)