## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, May 12, 2022, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Hung Hoang

## Hardness of Approximating the Rank of a Graph Divisor

Graph divisor theory is a combinatorial analogue of the divisor theory in algebraic geometry. A fundamental concept in this area is the rank of a graph divisor. It is already known that computing the rank is NP-hard (Kiss and Tóthmérész, 2015). By a reduction from the Minimum Target Set Selection problem, we show that no polynomial-time algorithm can approximate the rank within the factor of 2^{O(log^{1-ε}n)} unless P = NP, and assuming a weaker conjecture (the Planted Dense Subgraph Conjecture), there is no polynomial time O(n^{1/2-ε})-approximation

Joint work with Kristóf Bérczi and Lilla Tóthmérész.

Information for students and suggested topics for student talks