The Parameterized Complexity of the k -Biclique Problem

DOI10.1145/3212622zbMath1426.68131OpenAlexW2893188841MaRDI QIDQ4625655

Bingkai Lin

Publication date: 25 February 2019

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3212622

zbMATH Keywords

probabilistic methodexponential time hypothesisdichotomy theorembicliquemaximum \(k\)-subset intersectionparameterized inapproximabilityWeil's character sum theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (10)

Quasipolynomiality of the Smallest Missing Induced Subgraph ⋮ Computing dense and sparse subgraphs of weakly closed graphs ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Unnamed Item ⋮ On closest pair in Euclidean metric: monochromatic is as hard as bichromatic ⋮ Parameterized Dynamic Variants of Red-Blue Dominating Set ⋮ Hardness and tractability of the \(\gamma\)\textsf{-Complete Subgraph} problem ⋮ Parameterized counting of partially injective homomorphisms ⋮ A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction

This page was built for publication: The Parameterized Complexity of the k -Biclique Problem