A new graph parameter and its relation to approximation properties of graph H-colouring
Johan Thapper

04 May 2012, 14:30 Salle/Bat : 445/PCRI-N
Contact :

Activités de recherche :

Résumé :

A homomorphism between graphs G and H is a vertex map from G to H that
carries edges in G to edges in H. A (proper) k-colouring of a graph G
can be seen as a homomorphism form G to K_k. From this point of view,
a natural generalisation of graph colouring is obtained by replacing
K_k by some arbitrary (but fixed) graph H. This is the graph
homomorphism problem with a fixed target graph H, also called the
H-Colouring Problem. The optimisation version of this problem, the
Maximum H-Colourable Subgraph Problem (Max H-Col), is the problem
where one seeks a vertex map from G to H that maximises the number of
edges in G mapped edges in H. For the complete graph H = K_k, this
problem has been studied under the name Max k-cut. Max k-cut is
APX-complete but approximation algorithms exist that are conjectured
to have optimal performance.

I will present a simple approximation-preserving reduction between
Max H-Col problems that gives rise to a binary graph parameter with
interesting properties. The parameter is used to relate the
approximation ratios of different Max H-Col problems; in other words,
it allows the translation of approximability (and non-approximability)
results for one problem into (non)-approximability results for other
problems with a degradation in precision determined by the
parameter. Using the known approximation algorithms for Max k-cut in
combination with this reduction, I will show how to obtain general
asymptotic approximability results for Max H-Col.

Furthermore, I will discuss a close connection to work by Robert Smal
on cubical colourings of graphs. This connection provides a different
way of computing the parameter and raises a number of interesting
questions.

The talk is based on joint work with Robert Engstrm, Tommy Frnqvist,
and Peter Jonsson (Linkping University, Sweden).

Semantic approaches to predict the presence of asb
Integration of Data and Knowledge
Monday 08 November 2021 - 13:00
Salle : 455 - PCRI-N
Thamer Mecharnia
.............................................