Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) Algo
A new graph parameter and its relation to approximation properties of graph H-colouring
Johan Thapper

04 May 2012, 14h30
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).

Pour en savoir plus : http://www.lix.polytechnique.fr/~thapper/
Séminaires
Programmation mathématique multi-objectif pour la
Thursday 13 December 2018 - 14h30
Salle : unknown - unknown
Audrey Legendre .............................................

Redundancy in Distributed Proofs
Algorithmique distribuée
Tuesday 04 December 2018 - 00h00
Salle : 465 - PCRI-N
Ami Paz .............................................

Some recent results on the integer linear programm
Théorie des graphes
Friday 30 November 2018 - 00h00
Salle : 445 - PCRI-N
Hung Nguyen .............................................

Scalable and exhaustive screening of metabolic fun
Wednesday 28 November 2018 - 11h00
Salle : 465 - PCRI-N
Clémence Frioux .............................................

Studying the three-dimensional structure of DNA fr
Thursday 22 November 2018 - 15h00
Salle : unknown - unknown
Nelle Varoquaux .............................................