2021/11/10 by Bukh, Boris, S., Karthik C., Narayanan, Bhargav
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2111.05518
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.