Efficient computation of generalized Ising polynomials on graphs with fixed clique-width

Autor:	Kotek, Tomer, Makowsky, Johann A.
Rok vydání:	2015
Předmět:	Computer Science - Logic in Computer Science 05C31 F.4.1 F.2.2 G.2.2
Druh dokumentu:	Working Paper
Popis:	Graph polynomials which are definable in Monadic Second Order Logic (MSOL) on the vocabulary of graphs are Fixed-Parameter Tractable (FPT) with respect to clique-width. In contrast, graph polynomials which are definable in 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 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 MSOL on the vocabulary of graphs and prove that they are Fixed-Parameter Polynomial Time (FPPT) 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. Comment: 12 pages, 1 figure
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1505.06617 Zobrazit plný text záznamu View this record from Arxiv