Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds

Meirav Zehavi (BGU, Beersheba)

17-Nov-2020, 17:30-18:00 (3 years ago)

Abstract: We prove that the Hadwiger number of an $n$-vertex graph $G$ (the maximum size of a clique minor in $G$) cannot be computed in time $n^{o(n)}$, unless the Exponential Time Hypothesis (ETH) fails. This resolves a well-known open question in the area of exact exponential algorithms. The technique developed for resolving the Hadwiger number problem has a wider applicability. We use it to rule out the existence of $n^{o(n)}$-time algorithms (up to ETH) for a large class of computational problems concerning edge contractions in graphs.

Joint work with Fomin, Lokshtanov, Mihajlin and Saurabh.

discrete mathematicscombinatorics

Audience: researchers in the discipline

( paper | slides | video )


LA Combinatorics and Complexity Seminar

Series comments: Password is on the seminar page. www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm

Organizers: Igor Pak*, Greta Panova
*contact for this listing

Export talk to