Beating treewidth for average-case subgraph isomorphism

DOI10.1007/s00453-021-00813-yOpenAlexW2997589087MaRDI QIDQ2041983

Gregory Rosenthal

Publication date: 26 July 2021

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

circuit complexitysubgraph isomorphismaverage-case complexity\(\mathrm{AC}^0\)

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items

Tree-Depth and the Formula Complexity of Subgraph Isomorphism

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits
• On the complexity of fixed parameter clique and dominating set
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• The treewidth and pathwidth of hypercubes
• A partial k-arboretum of graphs with bounded treewidth
• On an isoperimetric problem for Hamming graphs
• Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\)
• Which problems have strongly exponential complexity?
• Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
• Parameters Tied to Treewidth
• Sparse Balanced Partitions and the Complexity of Subgraph Problems
• Expander graphs and their applications
• Graph minors. II. Algorithmic aspects of tree-width
• Poisson approximation for large deviations
• Color-coding
• LOWER BOUNDS FOR SUBGRAPH ISOMORPHISM
• The Monotone Complexity of $k$-Clique on Random Graphs
• On the $AC^0$ Complexity of Subgraph Isomorphism