{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:39:16Z","timestamp":1787323156592,"version":"build-2736575974"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/S016562\/1"],"award-info":[{"award-number":["EP\/S016562\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/S016694\/1"],"award-info":[{"award-number":["EP\/S016694\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N019660\/1"],"award-info":[{"award-number":["EP\/N019660\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Jerrum, Sinclair, and Vigoda [ J. ACM, 51 (2004), pp. 671--697] showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition function of edge-weighted matchings in a bipartite graph. Equivalently, this may be viewed as approximating the partition function of vertex-weighted independent sets in the line graph of a bipartite graph. Line graphs of bipartite graphs are perfect graphs and are known to be precisely the class of (claw, diamond, odd hole)-free graphs. So how far does the result of Jerrum, Sinclair, and Vigoda extend? We first show that it extends to (claw, odd hole)-free graphs, and then show that it extends to the even larger class of (fork, odd hole)-free graphs. Our techniques are based on graph decompositions, which have been the focus of much recent work in structural graph theory, and on structural results of Chv\u00e1tal and Sbihi [ J. Combin. Theory Ser. B, 44 (1988)], Maffray and Reed [ J. Combin. Theory Ser. B, 75 (1999)], and Lozin and Milani\u010d [ J. Discrete Algorithms, 6 (2008), pp. 595--604].<\/jats:p>","DOI":"10.1137\/20m1347747","type":"journal-article","created":{"date-parts":[[2021,6,24]],"date-time":"2021-06-24T10:34:01Z","timestamp":1624530841000},"page":"1503-1524","source":"Crossref","is-referenced-by-count":5,"title":["Counting Weighted Independent Sets beyond the Permanent"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2018-0374","authenticated-orcid":true,"given":"Martin","family":"Dyer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0863-7279","authenticated-orcid":true,"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1123-1774","authenticated-orcid":true,"given":"Haiko","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kristina","family":"Vu\u0161kovi\u0107","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,6,24]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(70)80019-9"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/050644033"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2004.06.019"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"A. Brandst\u00e4dt, V. B. Le, and J. P. Spinrad,\n                      Graph Classes: A Survey\n                      , SIAM Discrete Math. Appl., SIAM, Philadelphia, 1999.","DOI":"10.1137\/1.9780898719796"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0012-8"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21732"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2006.164.51"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.06.001"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.07.005"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90085-8"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , Grad. Texts Math. 173, Springer, New York, 2012,https:\/\/doi.org\/10.1007\/978-3-662-53622-3.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"M. Dyer, C. Greenhill, and H. M\u00fcller,\n                      Counting Independent Sets in Graphs with Bounded Bipartite Pathwidth\n                      , 2019,https:\/\/arxiv.org\/abs\/1812.03195.","DOI":"10.1007\/978-3-030-30786-8_23"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/2629600"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020961"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , Algorithms Combin., Springer, New York, 1988,https:\/\/doi.org\/10.1007\/978-3-642-97881-4.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2010.01.001"},{"key":"atypb19","first-page":"19","volume":"1","author":"Harary F.","year":"1974","journal-title":"Rev. Soc. Mat. Chile"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"M. Jerrum,\n                      Counting, Sampling and Integrating: Algorithms and Complexity\n                      , Lect. Math.ETH Z\u00fcrich, Birkh\u00e4user, Basel, 2003.","DOI":"10.1007\/978-3-0348-8005-3"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"atypb25","first-page":"3","author":"Kelly D.","year":"1985","journal-title":"Dordrecht"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321853"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"V. V. Lozin and M. Milani\u010d,\n                      A polynomial algorithm to find an independent set of maximum weight in a fork-free graph\n                      , in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, ACM Press, 2006, pp. 26-30,http:\/\/dl.acm.org\/citation.cfm?id=1109557.1109561.","DOI":"10.1145\/1109557.1109561"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.04.001"},{"key":"atypb29","author":"Maffray F.","year":"2001","journal-title":"Perfect Graphs, J. L. Ramirez-Alfonsi and B. A. Reed, eds., Wiley, New York"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1998.1872"},{"key":"atypb31","unstructured":"J. Matthews,\n                      Markov Chains for Sampling Matchings\n                      , PhD thesis, University of Edinburgh, UK, 2008."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90074-X"},{"key":"atypb33","unstructured":"P. Nobili and A. Sassano,\n                      An $\\mathcal{O}(n^2\\log(n))$ Algorithm for the Weighted Stable Set Problem in Claw-Free Graphs\n                      , 2019,https:\/\/arxiv.org\/abs\/1501.05775."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90051-2"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"M. Tedder, D. G. Corneil, M. Habib, and C. Paul,\n                      Simpler linear-time modular decomposition via recursive factorizing permutations\n                      , in Proceedings of the 35th International Colloquium Automata, Languages and Programming, ICALP 2008, Reykjavik, Iceland, I. Damg\\aard, L. A. Goldberg, M. M. Halld\u00f3rsson, A. Ing\u00f3lfsd\u00f3ttir, and I. Walukiewicz, eds., Lecture Notes in Comput. Sci. 5125, Springer, New York, 2008, pp. 634-645,https:\/\/doi.org\/10.1007\/978-3-540-70575-8_52.","DOI":"10.1007\/978-3-540-70575-8_52"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01593791"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"G. Valiente,\n                      Algorithms on Trees and Graphs\n                      , Springer, New York, 2002,https:\/\/doi.org\/10.1007\/978-3-662-04921-1.","DOI":"10.1007\/978-3-662-04921-1"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"D. \u0160tefankovi\u010d, E. Vigoda, and J. Wilmes,\n                      On counting perfect matchings in general graphs\n                      , in Proceedings of the 13th Latin American Symposium on Theoretical Informatics, Buenos Aires, Argentina, 2018, M. A. Bender, M. Farach-Colton, and M. A. Mosteiro, eds., Lecture Notes in Comput. Sci. 10807, Springer, New York, 2018, pp. 873-885,https:\/\/doi.org\/10.1007\/978-3-319-77404-6_63.","DOI":"10.1007\/978-3-319-77404-6_63"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1347747","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:45:08Z","timestamp":1787319908000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1347747"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1347747"],"URL":"https:\/\/doi.org\/10.1137\/20m1347747","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}