I imagine they're trying to say you can't have a sub-linear approach, because it...

cschmidt on June 9, 2022 | parent | context | favorite | on: Researchers achieve ‘absurdly fast’ algorithm for ...

I imagine they're trying to say you can't have a sub-linear approach, because it takes linear time to specify the graph (going over it once). So the time to "write it down" is the best you can possibly do (for an exact method).