文章基本信息

标题：OV Graphs Are (Probably) Hard Instances
本地全文：下载
作者：Josh Alman ; Virginia Vassilevska Williams
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：151
页码：1-18
DOI：10.4230/LIPIcs.ITCS.2020.83
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：A graph G on n nodes is an Orthogonal Vectors (OV) graph of dimension d if there are vectors v_1, â¦, v_n â^^ {0,1}^d such that nodes i and j are adjacent in G if and only if âY¨v_i,v_jâY© = 0 over Z. In this paper, we study a number of basic graph algorithm problems, except where one is given as input the vectors defining an OV graph instead of a general graph. We show that for each of the following problems, an algorithm solving it faster on such OV graphs G of dimension only d=O(log n) than in the general case would refute a plausible conjecture about the time required to solve sparse MAX-k-SAT instances: - Determining whether G contains a triangle. - More generally, determining whether G contains a directed k-cycle for any k â¥ 3. - Computing the square of the adjacency matrix of G over â"¤ or ?_2. - Maintaining the shortest distance between two fixed nodes of G, or whether G has a perfect matching, when G is a dynamically updating OV graph. We also prove some complementary results about OV graphs. We show that any problem which is NP-hard on constant-degree graphs is also NP-hard on OV graphs of dimension O(log n), and we give two problems which can be solved faster on OV graphs than in general: Maximum Clique, and Online Matrix-Vector Multiplication.
关键词：Orthogonal Vectors; Fine-Grained Reductions; Cycle Finding