Stanislav Busygin, Dmitrii V. Pasechnik

We show that for a graph G it is NP-hard to decide whether its independence number alpha(G) equals its clique partition number ~chi(G) even when some minimum clique partition of G is given. This implies that any alpha(G)-upper bound provably better than ~chi(G) is NP-hard to compute.

To establish this ... more >>>

Till Tantau

This paper introduces logspace optimisation problems as

analogues of the well-studied polynomial-time optimisation

problems. Similarly to them, logspace

optimisation problems can have vastly different approximation

properties, even though the underlying existence and budget problems

have the same computational complexity. Numerous natural problems

are presented that exhibit such a varying ...
more >>>