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

2015/05/25 by Kotek, Tomer, Makowsky, Johann A.
#05C31 #F.2.2 #F.4.1 #FOS: Computer and information sciences #G.2.2 #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1505.06617

Abstract

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.

Related

• Computation of Graph Polynomials via Tree Decomposition: Theory, Algorithms, and Python Implementation
• A logician's view of graph polynomials
• On the Parameterized Complexity of Graph Modification to First-Order Logic Properties
• On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic
• Computability by Monadic Second-Order Logic