Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01446257
Contributor : Hal Ifip <>
Submitted on : Wednesday, January 25, 2017 - 4:50:39 PM
Last modification on : Sunday, December 31, 2017 - 9:44:02 AM
Document(s) archivé(s) le : Wednesday, April 26, 2017 - 2:57:59 PM

File

385217_1_En_10_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Tomer Kotek, Johann Makowsky. Efficient Computation of Generalized Ising Polynomials on Graphs with Fixed Clique-Width. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. pp.135-146, ⟨10.1007/978-3-319-28678-5_10⟩. ⟨hal-01446257⟩

Share

Metrics

Record views

71

Files downloads

137