Równoważności pomiędzy zliczaniem trójkątów a problemami na przedziałach

Dowodzimy redukcji pomiędzy problemami na przedziałach a problemami dotyczącym zliczania i wypisywania trójkątów w grafach. Wskazujemy ogólne warunki, jakie musi spełniać problem na przedziałach, aby należeć do wprowadzonej przez nas klasy. Pokazujemy, że wszystkie takie problemy są równoważne (z dokładnością do czynników polilogarytmicznych) do siebie wzajemnie oraz do problemu zliczania trójkątów przechodzących przez dane krawędzie grafu.Analizujemy zależności pomiędzy problemami dotyczącymi trójkątów. Wskazujemy redukcje pomiędzy wypisywaniem trójkątów a wariantami problemów dotyczących ich znajdowania i zliczania, tworząc drugą klasę równoważnych sobie problemów. Jako uboczny efekt tych redukcji, otrzymujemy również nowy algorytm wypisywania trójkątów o takiej samej złożoności jak najlepszy znany algorytm rozwiązujący ten problem.Otrzymane równoważności pociągają ograniczenia górne oraz warunkowe (oparte o Hipotezę 3SUM) ograniczenia dolne dla złożoności czasowej problemów z naszej klasy z dokładnością do czynników polilogarytmicznych. Te wartości zrównały by się, gdyby zachodziło , w którym to przypadku złożoność tych problemów była by ostatecznie rozstrzygnięta. Pokazujemy nowy algorytm rozwiązywania problemów na przedziałach, który uogólnia powyższy czas działania na problemy online oraz na instancje których złożoność zdefiniowana jest za pomocą dwóch parametrów, osiągając na wszystkich klasach wejść lepszą złożoność czasową niż obecnie znane algorytmy.

We establish a set of fine-grained reductions between range query problems and the problems of counting and listing triangles in graphs. We show general conditions for range query problems to belong to our complexity class and prove that all such problems are equivalent\n (up to polylogarithmic factors) to each other and to the~problem of~per-edge counting of~triangles in graphs.We further analyse the relationships within the family of triangle problems, showing reductions between the triangle listing and per-edge triangle detection and counting, establishing a~second class of equivalent problems. As a byproduct, our proofs also produce an alternative simple triangle listing algorithm matching the complexity of the state-of-the-art solution.The obtained equivalences demonstrate, up to polylogarithmic factors, the upper bounds of and~the conditional 3SUM-based lower bounds of for the problems in our class. Those~two figures would match if , in which case the complexity of the range query problems would be settled. We create an algorithm matching this running time and extending it to online problems as well as to problems defined in terms of two parameters, improving upon the running time of existing algorithms for all classes of inputs.