2021/11/10 by Boris Bukh, Bukh, Boris, Karthik C. S. +4 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algebraic number #Bipartite graph #Combinatorics #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Discrete mathematics #FOS: Computer and information sciences #FOS: Mathematics #Graph #Integer (computer science) #Intersection (aeronautics) #Intersection graph #Limits and Structures in Graph Theory #Line graph #Mathematics #Parameterized complexity #Vertex (graph theory) #cs.CC #math.CO
paper · pdf · doi:10.48550/arxiv.2111.05518
published in arXiv (Cornell University) (Cornell University) · Abstract in metadata shortened to meet arxiv requirements
arxiv created 2021/11/10 · openalex publication_date 2021/11/10 · arxiv updated 2021/11/11 · openalex created_date 2022/07/25 · openalex updated_date 2026/08/08
In this paper, we show how one may (efficiently) construct two types of extremal combinatorial objects whose existence was previously conjectural. (*) Panchromatic Graphs: For fixed integer k, a k-panchromatic graph is, roughly speaking, a balanced bipartite graph with one partition class equipartitioned into k colour classes in which the common neighbourhoods of panchromatic k-sets of vertices are much larger than those of k-sets that repeat a colour. The question of their existence was raised by Karthik and Manurangsi [Combinatorica 2020]. (*) Threshold Graphs: For fixed integer k, a k-threshold graph is, roughly speaking, a balanced bipartite graph in which the common neighbourhoods of k-sets of vertices on one side are much larger than those of (k+1)-sets. The question of their existence was raised by Lin [JACM 2018]. As applications of our constructions, we show the following conditional time lower bounds on the parameterized set intersection problem where, given a collection of n sets over universe [n] and a parameter k, the goal is to find k sets with the largest intersection. (*) Assuming ETH, for any computable function F, no no(k)-time algorithm can approximate the parameterized set intersection problem up to factor F(k). This improves considerably on the previously best-known result under ETH due to Lin [JACM 2018], who ruled out any no(√(k)) time approximation algorithm for this problem. (*) Assuming SETH, for every ε>0 and any computable function F, no nk-ε-time algorithm can approximate the parameterized set intersection problem up to factor F(k). No result of comparable strength was previously known under SETH, even for solving this problem exactly.