The flip-width subpolynomial collapse conjecture
The flip-width subpolynomial collapse conjecture
Let be a hereditary graph class. For each , let denote the flip-width of for robber speed .
Flip-width subpolynomial collapse conjecture. The following conditions are equivalent:
- has almost bounded flip-width, that is, for every fixed and ,
for all ; 2. for every fixed ,
for all .
This predicts a collapse from the subpolynomial bound at exponent to subpolynomial bounds at every positive exponent. The source presents it as a conjecture supported by the paper's evidence; its general validity remains open.
Sources & referencesView supporting material
Primary source
Szymon Toruńczyk, “Flip-width: Cops and Robber on dense graphs”, arXiv:2302.00352 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.