2026-07-23T17:33:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25431 2026-03-19T13:28:25Z ddc:004 open_access

Bridging Weighted First Order Model Counting and Graph Polynomials Kuang, Qipeng Kuželka, Ondřej Wang, Yuanhong Wang, Yuyi Weighted First-Order Model Counting Axiom Enumerative Combinatorics Tutte Polynomial The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. It can be solved in time polynomial in the domain size for sentences from the two-variable fragment with counting quantifiers, known as C^2. This polynomial-time complexity is known to be retained when extending C^2 by one of the following axioms: linear order axiom, tree axiom, forest axiom, directed acyclic graph axiom or connectedness axiom. An interesting question remains as to which other axioms can be added to the first-order sentences in this way. We provide a new perspective on this problem by associating WFOMC with graph polynomials. Using WFOMC, we define Weak Connectedness Polynomial and Strong Connectedness Polynomials for first-order logic sentences. It turns out that these polynomials have the following interesting properties. First, they can be computed in polynomial time in the domain size for sentences from C^2. Second, we can use them to solve WFOMC with all of the existing axioms known to be tractable as well as with new ones such as bipartiteness, strong connectedness, having k connected components, etc. Third, the well-known Tutte polynomial can be recovered as a special case of the Weak Connectedness Polynomial, and the Strict and Non-Strict Directed Chromatic Polynomials can be recovered from the Strong Connectedness Polynomials. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Qipeng Kuang and Ondřej Kuželka and Yuanhong Wang and Yuyi Wang 2026 Is Part Of LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2026.7 urn:nbn:de:0030-drops-254316 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.7 eng https://creativecommons.org/licenses/by/4.0/legalcode