The exponential time hypothesis and the parameterized clique problem

DOI10.1007/978-3-642-33293-7_4MaRDI QIDQ4899237zbMATH OpenOpenAlexFDO

Authors Yijia Chen, Kord Eickmeyer, Jörg Flum

Publication date 7 January 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-33293-7_4

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Sparsification and subexponential approximation
• On parameterized exponential time complexity
• On hardness of approximating the parameterized clique problem
• Linear FPT reductions and computational lower bounds

Cited in

(9)

• Exact exponential-time algorithms for finding bicliques
• Boolean functional synthesis: hardness and practical algorithms
• An exact exponential time algorithm for counting bipartite cliques
• Lower bounds based on the exponential time hypothesis
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Maximum bipartite subgraphs of geometric intersection graphs
• Tractable representations for Boolean functional synthesis
• Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity

This page was built for publication: The exponential time hypothesis and the parameterized clique problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4899237)