{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T03:01:23Z","timestamp":1773802883917,"version":"3.50.1"},"reference-count":0,"publisher":"Association for the Advancement of Artificial Intelligence (AAAI)","issue":"23","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AAAI"],"abstract":"<jats:p>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. Conditioning WFOMC on evidence\u2014fixing the truth values of a set of ground literals\u2014has been shown impossible in time polynomial in the domain size (unless \u266fP \u2286 FP) even for fragments of logic that are otherwise tractable for WFOMC without evidence. In this work, we address the barrier by restricting the binary evidence to the case where the underlying Gaifman graph has bounded treewidth. We present a polynomial-time algorithm in the domain size for computing WFOMC for the two-variable fragments ??\u00b2 and ?\u00b2 conditioned on such binary evidence. Furthermore, we show the applicability of our algorithm in combinatorial problems by solving the stable seating arrangement problem on bounded-treewidth graphs of bounded degree, which was an open problem. We also conducted experiments to show the scalability of our algorithm compared to the existing model counting solvers.<\/jats:p>","DOI":"10.1609\/aaai.v40i23.38994","type":"journal-article","created":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:07:06Z","timestamp":1773796026000},"page":"19198-19207","source":"Crossref","is-referenced-by-count":0,"title":["Tractable Weighted First-Order Model Counting with Bounded Treewidth Binary Evidence"],"prefix":"10.1609","volume":"40","author":[{"given":"V\u00e1clav","family":"K\u016fla","sequence":"first","affiliation":[]},{"given":"Qipeng","family":"Kuang","sequence":"additional","affiliation":[]},{"given":"Yuyi","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Yuanhong","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Ond\u0159ej","family":"Ku\u017eelka","sequence":"additional","affiliation":[]}],"member":"9382","published-online":{"date-parts":[[2026,3,14]]},"container-title":["Proceedings of the AAAI Conference on Artificial Intelligence"],"original-title":[],"link":[{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/38994\/42956","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/38994\/42956","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:07:06Z","timestamp":1773796026000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/38994"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,14]]},"references-count":0,"journal-issue":{"issue":"23","published-online":{"date-parts":[[2026,3,17]]}},"URL":"https:\/\/doi.org\/10.1609\/aaai.v40i23.38994","relation":{},"ISSN":["2374-3468","2159-5399"],"issn-type":[{"value":"2374-3468","type":"electronic"},{"value":"2159-5399","type":"print"}],"subject":[],"published":{"date-parts":[[2026,3,14]]}}}