Lilla Tóthmérész: It is hard to approximate the rank of a graph divisor

EGERVÁRY SZEMINÁRIUM

Abstract: Graph divisor theory is a combinatorial analogue of the
divisor theory of algebraic geometry where the analogue of some of the
main theorems hold. The rank of a graph divisor is the fundamental
definition in this area, and it is a completely combinatorial
definition. It is already known that computing the rank is NP-hard.
Now we show that there is no polynomial time log n approximation for
the rank if NP\neq co-NP, and assuming a weaker conjecture of
complexity theory (the planted dense subgraph conjecture) there is a
constant c such that there is no polynomial time n^c -approximation.