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

DOI10.1007/978-3-319-28678-5_10MaRDI QIDQ2798025zbMATH OpenOpenAlexFDO

Authors Tomer Kotek, Johann A. Makowsky

Publication date 1 April 2016

Published in Topics in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.06617

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph polynomials (05C31) Logic in computer science (03B70)

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.

Recommendations

• Computing Graph Polynomials on Graphs of Bounded Clique-Width
• Farrell polynomials on graphs of bounded tree width
• Computing the Tutte Polynomial on Graphs of Bounded Clique‐Width
• Graph-Theoretic Concepts in Computer Science
• A multivariate interlace polynomial and its computation for graphs of bounded clique-width

Cited in

(1)

• Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs

This page was built for publication: Efficient computation of generalized Ising polynomials on graphs with fixed clique-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2798025)