The Fine-Grained Complexity of Multi-Dimensional Ordering Properties

Autor: Nina, Maria Paula Parga, An, Haozhe, Gurumukhani, Mohit, Impagliazzo, Russell, Jaber, Michael, Künnemann, Marvin, Parga Nina, Maria Paula
Přispěvatelé: Golovach, Petr A., Zehavi, Meirav
Rok vydání: 2022
Předmět:
Zdroj: 16th International Symposium on Parameterized and Exact Computation
Leibniz International Proceedings in Informatics
Leibniz International Proceedings in Informatics (LIPIcs), 214
16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
ISSN: 1432-0541
0178-4617
1868-8969
DOI: 10.1007/s00453-022-01014-x
Popis: We define a class of problems whose input is an n-sized set of d-dimensional vectors, and where the problem is first-order definable using comparisons between coordinates. This class captures a wide variety of tasks, such as complex types of orthogonal range search, model-checking first-order properties on geometric intersection graphs, and elementary questions on multidimensional data like verifying Pareto optimality of a choice of data points. Focusing on constant dimension d, we show that any k-quantifier, d-dimensional such problem is solvable in O(n^{k-1} log^{d-1} n) time. Furthermore, this algorithm is conditionally tight up to subpolynomial factors: we show that assuming the 3-uniform hyperclique hypothesis, there is a k-quantifier, (3k-3)-dimensional problem in this class that requires time Ω(n^{k-1-o(1)}). Towards identifying a single representative problem for this class, we study the existence of complete problems for the 3-quantifier setting (since 2-quantifier problems can already be solved in near-linear time O(nlog^{d-1} n), and k-quantifier problems with k > 3 reduce to the 3-quantifier case). We define a problem Vector Concatenated Non-Domination VCND_d (Given three sets of vectors X,Y and Z of dimension d,d and 2d, respectively, is there an x ∈ X and a y ∈ Y so that their concatenation x∘y is not dominated by any z ∈ Z, where vector u is dominated by vector v if u_i ≤ v_i for each coordinate 1 ≤ i ≤ d), and determine it as the "unique" candidate to be complete for this class (under fine-grained assumptions).
Leibniz International Proceedings in Informatics (LIPIcs), 214
ISSN:1868-8969
16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
ISBN:978-3-95977-216-7
Databáze: OpenAIRE
Externí odkaz: