Content deleted Content added
added more fgc sources |
→Implications of conjectured hardness: noted that some lower bounds already known |
||
Line 33:
=== Implications of conjectured hardness ===
The OMv conjecture implies lower bounds on the time needed to solve a large class of dynamic graph problems, including [[reachability]] and [[Connectivity (graph theory)|connectivity]], [[Shortest path problem|shortest path]], and subgraph detection. For many of these problems, the implied lower bounds have matching upper bounds.<ref name=":0" /> While some of these lower bounds also followed from previous conjectures (e.g., [[3SUM]]),<ref>{{Cite journal |last=Abboud |first=Amir |last2=Williams |first2=Virginia Vassilevska |title=Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems |url=https://ieeexplore.ieee.org/document/6979028 |journal=FOCS '14|pages=434–443 |doi=10.1109/FOCS.2014.53 |isbn=978-1-4799-6517-5}}</ref> many of the lower bounds that follow from OMv are stronger or new.
Later work showed that the OMv conjecture implies lower bounds on the time needed for subgraph counting in [[Average-case complexity|average-case]] graphs.<ref name=":1">{{Cite journal |last=Henzinger |first=Monika |last2=Lincoln |first2=Andrea |last3=Saha|first3=Barna |title=The Complexity of Average-Case Dynamic Subgraph Counting |url=https://doi.org/10.1137/1.9781611977073.23 |journal=ACM-SIAM Symposium on Discrete Algorithms (SODA) |series=SODA '22 |pages=459–498 |doi=10.1137/1.9781611977073.23 }}</ref>
== References ==
| |||