Forbidden configurations: Finding the number predicted by the Anstee-Sali conjecture is NP-hard

DOI10.26493/1855-3974.438.300zbMath1337.05107arXiv1210.8189OpenAlexW2172290322WikidataQ123301546 ScholiaQ123301546MaRDI QIDQ2810375

Miguel Raggi

Publication date: 1 June 2016

Published in: Ars Mathematica Contemporanea (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphtraceNP-hardNP-completeforbidden configurationAnstee-Sali conjecture

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Extremal set theory (05D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

This page was built for publication: Forbidden configurations: Finding the number predicted by the Anstee-Sali conjecture is NP-hard