Efficient Computation of Generalized Ising Polynomials on Graphs with Fixed Clique-Width

Abstract : Graph polynomials which are definable in Monadic Second Order Logic ($\mathrm {MSOL}$) on the vocabulary of graphs are Fixed-Parameter Tractable ($\mathrm {FPT}$) with respect to clique-width. In contrast, graph polynomials which are definable in $\mathrm {MSOL}$ on the vocabulary of hypergraphs are fixed-parameter tractable with respect to tree-width, but not necessarily with respect to clique-width. No algorithmic meta-theorem is known for the computation of graph polynomials definable in $\mathrm {MSOL}$ on the vocabulary of hypergraphs with respect to clique-width. We define an infinite class of such graph polynomials extending the class of graph polynomials definable in $\mathrm {MSOL}$ on the vocabulary of graphs and prove that they are Fixed-Parameter Polynomial Time ($\mathrm {FPPT}$ or $\mathrm {XP}$) computable, i.e. that they can be computed in time $O(n^{f(k)})$, where n is the number of vertices and k is the clique-width.
Type de document :
Communication dans un congrès
Mohammed Taghi Hajiaghayi; Mohammad Reza Mousavi. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. Lecture Notes in Computer Science, LNCS-9541, pp.135-146, 2016, Topics in Theoretical Computer Science. 〈10.1007/978-3-319-28678-5_10〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01446257
Contributeur : Hal Ifip <>
Soumis le : mercredi 25 janvier 2017 - 16:50:39
Dernière modification le : dimanche 31 décembre 2017 - 09:44:02
Document(s) archivé(s) le : mercredi 26 avril 2017 - 14:57:59

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Tomer Kotek, Johann Makowsky. Efficient Computation of Generalized Ising Polynomials on Graphs with Fixed Clique-Width. Mohammed Taghi Hajiaghayi; Mohammad Reza Mousavi. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. Lecture Notes in Computer Science, LNCS-9541, pp.135-146, 2016, Topics in Theoretical Computer Science. 〈10.1007/978-3-319-28678-5_10〉. 〈hal-01446257〉

Partager

Métriques

Consultations de la notice

17