An Approximability-related Parameter on Graphs - Properties and Applications
Robert Engström, Tommy Färnqvist, Peter Jonsson, Johan Thapper
Abstract
We introduce a binary parameter on optimisation problems called
separation. The parameter is used to relate the
approximation ratios of different optimisation problems; in other
words, we can convert approximability (and non-approximability) result
for one problem into (non)-approximability results for other problems.
Our main application is the problem (weighted) maximum
H-colourable subgraph (Max H-Col), which is a
restriction of the general maximum constraint satisfaction
problem (Max CSP) to a single, binary, and symmetric
relation. Using known approximation ratios for Max
k-cut, we obtain general asymptotic approximability
results for Max H-Col for an arbitrary graph H. For
several classes of graphs, we provide near-optimal results under the
unique games conjecture. We also investigate separation as a graph
parameter. In this vein, we study its properties on circular complete
graphs. Furthermore, we establish a close connection to work by
Šámal on cubical colourings of graphs. This
connection shows that our parameter is closely related to a special
type of chromatic number. We believe that this insight may turn out to
be crucial for understanding the behaviour of the parameter, and in
the longer term, for understanding the approximability of optimisation
problems such as Max H-Col.
Full Text: PDF PostScript