Parameterized Problems on Coincidence Graphs

Sylvain Guillemot 1
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A $(k,r)$-tuple is a word of length $r$ on an alphabet of size $k$. A graph is $(k,r)$-representable if we can assign a $(k,r)$-tuple to each vertex such that two vertices are connected iff the associated tuples agree on some component. We study the complexity of several graph problems on $(k,r)$-representable graphs, as a function of the parameters $k,r$; the problems under study are \textsc{Maximum Independent Set}, \textsc{Minimum Dominating Set} and \textsc{Maximum Clique}. In this framework, there are two classes of interest: the graphs representable with tuples of logarithmic length (\ie{} graphs $(k,r)$-representable with $r = O(k \log n)$), and the graphs representable with tuples of polynomial length (\ie{} graphs $(k,r)$-representable with $r = poly(n)$). In both cases, we show that the problems are computationally hard, though we obtain stronger hardness results in the second case. Our hardness results also allow us to derive optimality results for \textsc{Multidimensional Matching} and \textsc{Disjoint $r$-Subsets}.
Type de document :
Communication dans un congrès
Tetsuo Asano. ISAAC'06: International Symposium on Algorithms and Computation, Dec 2006, Kolkata, India, Springer, pp.253-266, 2006, Lecture Notes in Computer Science. 〈http://www.lirmm.fr/~mab〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00145457
Contributeur : Sylvain Guillemot <>
Soumis le : jeudi 10 mai 2007 - 13:33:56
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00145457, version 1

Collections

Citation

Sylvain Guillemot. Parameterized Problems on Coincidence Graphs. Tetsuo Asano. ISAAC'06: International Symposium on Algorithms and Computation, Dec 2006, Kolkata, India, Springer, pp.253-266, 2006, Lecture Notes in Computer Science. 〈http://www.lirmm.fr/~mab〉. 〈lirmm-00145457〉

Partager

Métriques

Consultations de la notice

67