{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,28]],"date-time":"2025-07-28T21:31:06Z","timestamp":1753738266864,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T00:00:00Z","timestamp":1728950400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T00:00:00Z","timestamp":1728950400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"CISPA - Helmholtz-Zentrum f\u00fcr Informationssicherheit gGmbH"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,1]]},"abstract":"Abstract<\/jats:title>\n In the general AntiFactor<\/jats:sc> problem, a graph G<\/jats:italic> and, for every vertex v<\/jats:italic> of G<\/jats:italic>, a set \n \n $$X_v\\subseteq {\\mathbb {N}}$$<\/jats:tex-math>\n \n \n \n X<\/mml:mi>\n v<\/mml:mi>\n <\/mml:msub>\n \u2286<\/mml:mo>\n N<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> of forbidden degrees is given. The task is to find a set S<\/jats:italic> of edges such that the degree of v<\/jats:italic> in S<\/jats:italic> is not<\/jats:italic> in the set \n \n $$X_v$$<\/jats:tex-math>\n \n \n X<\/mml:mi>\n v<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. Standard techniques (dynamic programming plus fast convolution) can be used to show that if M<\/jats:italic> is the largest forbidden degree, then the problem can be solved in time \n \n $$(M+2)^{{\\operatorname {tw}}}\\cdot n^{{\\mathcal {O}}(1)}$$<\/jats:tex-math>\n \n \n \n \n (<\/mml:mo>\n M<\/mml:mi>\n +<\/mml:mo>\n 2<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n tw<\/mml:mo>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> if a tree decomposition of width \n \n $${\\operatorname {tw}}$$<\/jats:tex-math>\n \n tw<\/mml:mo>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is given. However, significantly faster algorithms are possible if the sets \n \n $$X_v$$<\/jats:tex-math>\n \n \n X<\/mml:mi>\n v<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> are sparse: our main algorithmic result shows that if every vertex has at most \n \n $$x$$<\/jats:tex-math>\n \n x<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> forbidden degrees (we call this special case AntiFactor<\/jats:sc>\n x<\/jats:sub>), then the problem can be solved in time \n \n $$(x+1)^{{\\mathcal {O}}({\\operatorname {tw}})}\\cdot n^{{\\mathcal {O}}(1)}$$<\/jats:tex-math>\n \n \n \n \n (<\/mml:mo>\n x<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n \n O<\/mml:mi>\n (<\/mml:mo>\n tw<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. That is, AntiFactor<\/jats:sc>\n x<\/jats:sub> is fixed-parameter tractable parameterized by treewidth \n \n $${\\operatorname {tw}}$$<\/jats:tex-math>\n \n tw<\/mml:mo>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and the maximum number \n \n $$x$$<\/jats:tex-math>\n \n x<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> of excluded degrees. Our algorithm uses the technique of representative sets, which can be generalized to the optimization version, but (as expected) not to the counting version of the problem. In fact, we show that #AntiFactor<\/jats:sc>\n 1<\/jats:sub> is already #\n \n $$[1]$$<\/jats:tex-math>\n \n \n [<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-hard parameterized by the width of the given decomposition. Moreover, we show that, unlike for the decision version, the standard dynamic programming algorithm is essentially optimal for the counting version. Formally, for a fixed nonempty set \n \n $$X$$<\/jats:tex-math>\n \n X<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, we denote by \n \n $$X$$<\/jats:tex-math>\n \n X<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-AntiFactor<\/jats:sc> the special case where every vertex v<\/jats:italic> has the same set \n \n $$X_v=X$$<\/jats:tex-math>\n \n \n \n X<\/mml:mi>\n v<\/mml:mi>\n <\/mml:msub>\n =<\/mml:mo>\n X<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> of forbidden degrees. We show the following lower bound for every fixed set \n \n $$X$$<\/jats:tex-math>\n \n X<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>: if there is an \n \n $$\\epsilon >0$$<\/jats:tex-math>\n \n \n \u03f5<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> such that #\n \n $$X$$<\/jats:tex-math>\n \n X<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-AntiFactor<\/jats:sc> can be solved in time \n \n $$(\\max X+2-\\epsilon )^{{\\operatorname {tw}}}\\cdot n^{{\\mathcal {O}}(1)}$$<\/jats:tex-math>\n \n \n \n \n (<\/mml:mo>\n max<\/mml:mo>\n X<\/mml:mi>\n +<\/mml:mo>\n 2<\/mml:mn>\n -<\/mml:mo>\n \u03f5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n tw<\/mml:mo>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> given a tree decomposition of width \n \n $${\\operatorname {tw}}$$<\/jats:tex-math>\n \n tw<\/mml:mo>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, then the counting strong exponential-time hypothesis (#SETH) fails.\n<\/jats:p>","DOI":"10.1007\/s00453-024-01265-w","type":"journal-article","created":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T07:01:59Z","timestamp":1728975719000},"page":"22-88","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Anti-factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)"],"prefix":"10.1007","volume":"87","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5686-8314","authenticated-orcid":false,"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7443-9599","authenticated-orcid":false,"given":"Govind S.","family":"Sankar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5810-7949","authenticated-orcid":false,"given":"Philipp","family":"Schepper","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,15]]},"reference":[{"issue":"7","key":"1265_CR1","doi-asserted-by":"publisher","first-page":"1939","DOI":"10.1007\/s00453-020-00681-y","volume":"82","author":"A Agrawal","year":"2020","unstructured":"Agrawal, A., Jain, P., Kanesh, L., Saurabh, S.: Parameterized complexity of conflict-free matchings and paths. Algorithmica 82(7), 1939\u20131965 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00681-y","journal-title":"Algorithmica"},{"key":"1265_CR2","doi-asserted-by":"publisher","unstructured":"Alman, J., Williams, V.V.: A refined laser method and faster matrix multiplication. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u201313, 2021, pp. 522\u2013539. SIAM (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.32","DOI":"10.1137\/1.9781611976465.32"},{"key":"1265_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Dynamic programming on graphs with bounded treewidth. In: International Colloquium on Automata, Languages, and Programming, pp. 105\u2013118. Springer (1988)","DOI":"10.1007\/3-540-19488-6_110"},{"key":"1265_CR4","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L: Treewidth: algorithmic techniques and results. In: International Symposium on Mathematical Foundations of Computer Science, pp. 19\u201336. Springer (1997)","DOI":"10.1007\/BFb0029946"},{"key":"1265_CR5","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015). https:\/\/doi.org\/10.1016\/j.ic.2014.12.008","journal-title":"Inf. Comput."},{"issue":"3","key":"1265_CR6","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"HL Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51(3), 255\u2013269 (2008). https:\/\/doi.org\/10.1093\/comjnl\/bxm037","journal-title":"Comput. J."},{"issue":"10","key":"1265_CR7","doi-asserted-by":"publisher","first-page":"3890","DOI":"10.1007\/s00453-019-00579-4","volume":"81","author":"\u00c9 Bonnet","year":"2019","unstructured":"Bonnet, \u00c9., Brettell, N., Kwon, O., Marx, D.: Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms. Algorithmica 81(10), 3890\u20133935 (2019). https:\/\/doi.org\/10.1007\/s00453-019-00579-4","journal-title":"Algorithmica"},{"issue":"3","key":"1265_CR8","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1002\/rsa.20204","volume":"32","author":"M Bordewich","year":"2008","unstructured":"Bordewich, M., Dyer, M.E., Karpinski, M.: Path coupling using stopping times and counting independent sets and colorings in hypergraphs. Random Struct. Algorithms 32(3), 375\u2013399 (2008). https:\/\/doi.org\/10.1002\/rsa.20204","journal-title":"Random Struct. Algorithms"},{"key":"1265_CR9","unstructured":"Bubley, R., Dyer, M.E.: Graph orientations with no sink and an approximation for a hard case of #SAT. In: Saks, M.E. (ed.) Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5\u20137 January 1997, New Orleans, Louisiana, USA, pp. 248\u2013257. ACM\/SIAM (1997). http:\/\/dl.acm.org\/citation.cfm?id=314161.314263"},{"key":"1265_CR10","doi-asserted-by":"publisher","unstructured":"Cai, J., Huang, S., Lu, P.: From Holant to #CSP and back: dichotomy for $$\\text{Holant}^{c}$$ problems. In: Cheong, O., Chwa, K.-Y., Park, K. (ed) Algorithms and Computation\u201421st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15\u201317, 2010, Proceedings, Part I, Volume 6506 of Lecture Notes in Computer Science, pp. 253\u2013265. Springer (2010). https:\/\/doi.org\/10.1007\/978-3-642-17517-6_24","DOI":"10.1007\/978-3-642-17517-6_24"},{"issue":"23","key":"1265_CR11","doi-asserted-by":"publisher","first-page":"2468","DOI":"10.1016\/j.tcs.2010.10.039","volume":"412","author":"J Cai","year":"2011","unstructured":"Cai, J., Pinyan, L., Xia, M.: A computational proof of complexity of some restricted counting problems. Theor. Comput. Sci. 412(23), 2468\u20132485 (2011). https:\/\/doi.org\/10.1016\/j.tcs.2010.10.039","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1265_CR12","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0095-8956(88)90068-8","volume":"45","author":"G Cornu\u00e9jols","year":"1988","unstructured":"Cornu\u00e9jols, G.: General factors of graphs. J. Comb. Theory Ser. B 45(2), 185\u2013198 (1988). https:\/\/doi.org\/10.1016\/0095-8956(88)90068-8","journal-title":"J. Comb. Theory Ser. B"},{"key":"1265_CR13","doi-asserted-by":"publisher","unstructured":"Curticapean, R.: Block interpolation: a framework for tight exponential-time counting complexity. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming\u201442nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6\u201310, 2015, Proceedings, Part I, Volume 9134 of Lecture Notes in Computer Science, pp. 380\u2013392. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-662-47672-7_31","DOI":"10.1007\/978-3-662-47672-7_31"},{"key":"1265_CR14","doi-asserted-by":"publisher","unstructured":"Curticapean, R., Marx, D.: Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus. In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016, pp. 1650\u20131669. SIAM (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch113","DOI":"10.1137\/1.9781611974331.ch113"},{"key":"1265_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"1265_CR16","doi-asserted-by":"publisher","unstructured":"Dalmau, V., Ford, D.K.: Generalized satisfability with limited occurrences per variable: a study through delta-matroid parity. In: Rovan, B., Vojt\u00e1s, P. (eds.) Mathematical Foundations of Computer Science 2003, 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25\u201329, 2003, Proceedings, Volume 2747 of Lecture Notes in Computer Science, pp. 358\u2013367. Springer (2003). https:\/\/doi.org\/10.1007\/978-3-540-45138-9_30","DOI":"10.1007\/978-3-540-45138-9_30"},{"issue":"4","key":"1265_CR17","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/2635812","volume":"10","author":"H Dell","year":"2014","unstructured":"Dell, H., Husfeldt, T., Marx, D., Taslaman, N., Wahlen, M.: Exponential time complexity of the permanent and the Tutte polynomial. ACM Trans. Algorithms 10(4), 21:1-21:32 (2014). https:\/\/doi.org\/10.1145\/2635812","journal-title":"ACM Trans. Algorithms"},{"key":"1265_CR18","doi-asserted-by":"publisher","unstructured":"Dudycz, S., Paluch, K.: Optimal general matchings. In: Brandst\u00e4dt, A., K\u00f6hler, K., Meer, K. (eds.) Graph-Theoretic Concepts in Computer Science\u201444th International Workshop, WG 2018, Cottbus, Germany, June 27\u201329, 2018, Proceedings, Volume 11159 of Lecture Notes in Computer Science, pp. 176\u2013189. Springer (2018). Full version: arXiv:1706.07418. https:\/\/doi.org\/10.1007\/978-3-030-00256-5_15","DOI":"10.1007\/978-3-030-00256-5_15"},{"key":"1265_CR19","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449\u2013467 (1965). https:\/\/doi.org\/10.4153\/CJM-1965-045-4","journal-title":"Can. J. Math."},{"issue":"4","key":"1265_CR20","doi-asserted-by":"publisher","first-page":"47:1","DOI":"10.1145\/3396573","volume":"16","author":"E Eiben","year":"2020","unstructured":"Eiben, E., Kanj, I.: A colored path problem and its applications. ACM Trans. Algorithms 16(4), 47:1-47:48 (2020). https:\/\/doi.org\/10.1145\/3396573","journal-title":"ACM Trans. Algorithms"},{"issue":"251\u2013257","key":"1265_CR21","first-page":"22","volume":"12","author":"P Erd\u0151s","year":"1963","unstructured":"Erd\u0151s, P., Sachs, H.: Regul\u00e4re Graphen gegebener Taillenweite mit minimaler Knotenzahl. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. 12(251\u2013257), 22 (1963)","journal-title":"Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe."},{"issue":"4","key":"1265_CR22","doi-asserted-by":"publisher","first-page":"29:1","DOI":"10.1145\/2886094","volume":"63","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29:1-29:60 (2016). https:\/\/doi.org\/10.1145\/2886094","journal-title":"J. ACM"},{"issue":"3","key":"1265_CR23","doi-asserted-by":"publisher","first-page":"36:1","DOI":"10.1145\/3039243","volume":"13","author":"FV Fomin","year":"2017","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Representative families of product families. ACM Trans. Algorithms 13(3), 36:1-36:29 (2017). https:\/\/doi.org\/10.1145\/3039243","journal-title":"ACM Trans. Algorithms"},{"key":"1265_CR24","doi-asserted-by":"publisher","unstructured":"Guo, H., Lu, P.: On the complexity of Holant problems. In: Krokhin, A.A., Zivn\u00fd, S. (ed.) The Constraint Satisfaction Problem: Complexity and Approximability, Volume\u00a07 of Dagstuhl Follow-Ups, pp. 159\u2013177. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/DFU.Vol7.15301.6","DOI":"10.4230\/DFU.Vol7.15301.6"},{"issue":"4","key":"1265_CR25","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1265_CR26","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s00037-015-0118-3","volume":"25","author":"S Huang","year":"2016","unstructured":"Huang, S., Pinyan, L.: A dichotomy for real weighted Holant problems. Comput. Complex. 25(1), 255\u2013304 (2016). https:\/\/doi.org\/10.1007\/s00037-015-0118-3","journal-title":"Comput. Complex."},{"issue":"2","key":"1265_CR27","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1265_CR28","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s00224-016-9671-7","volume":"59","author":"M Kowalczyk","year":"2016","unstructured":"Kowalczyk, M., Cai, J.-Y.: Holant problems for 3-regular graphs with complex edge functions. Theory Comput. Syst. 59(1), 133\u2013158 (2016). https:\/\/doi.org\/10.1007\/s00224-016-9671-7","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"1265_CR29","doi-asserted-by":"publisher","first-page":"16:1","DOI":"10.1145\/3390887","volume":"67","author":"S Kratsch","year":"2020","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Representative sets and irrelevant vertices: new tools for kernelization. J. ACM 67(3), 16:1-16:50 (2020). https:\/\/doi.org\/10.1145\/3390887","journal-title":"J. ACM"},{"issue":"2","key":"1265_CR30","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/3170442","volume":"14","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms 14(2), 13:1-13:30 (2018). https:\/\/doi.org\/10.1145\/3170442","journal-title":"ACM Trans. Algorithms"},{"key":"1265_CR31","volume-title":"Matching Theory","author":"L Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. North-Holland Publishing Co., Amsterdam (1986). (Annals of Discrete Mathematics, 29)"},{"issue":"1\u20132","key":"1265_CR32","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/BF01889919","volume":"23","author":"L Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz, L.: The factorization of graphs. II. Acta Math. Hung. 23(1\u20132), 223\u2013246 (1972)","journal-title":"Acta Math. Hung."},{"key":"1265_CR33","first-page":"93","volume":"18","author":"P Lu","year":"2011","unstructured":"Lu, P.: Complexity dichotomies of counting problems. Electron. Colloquium Comput. Complex. 18, 93 (2011)","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"1265_CR34","unstructured":"Marx, D., Sankar, G.S., Schepper, P.: Anti-factor is FPT parameterized by treewidth and list size (but counting is hard). CoRR (2021). arXiv:2110.09369"},{"key":"1265_CR35","doi-asserted-by":"publisher","unstructured":"Marx, D., Sankar, G.S., Schepper, P.: Degrees and gaps: tight complexity results of general factor problems parameterized by treewidth and cutwidth. In: Bansal, N., Merelli, E., Worrell, J. (eds.) 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12\u201316, 2021, Glasgow, Scotland (Virtual Conference), Volume 198 of LIPIcs, pp. 95:1\u201395:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). Full version: arXiv:2105.08980. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.95","DOI":"10.4230\/LIPIcs.ICALP.2021.95"},{"key":"1265_CR36","doi-asserted-by":"publisher","unstructured":"Marx, D., Sankar, G.S., Schepper, P.: Anti-factor is FPT parameterized by treewidth and list size (but counting is hard). In: Dell, H., Nederlof, J. (eds.) 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, September 7\u20139, 2022, Potsdam, Germany, Volume 249 of LIPIcs, pp. 22:1\u201322:23. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2022.22","DOI":"10.4230\/LIPIcs.IPEC.2022.22"},{"key":"1265_CR37","doi-asserted-by":"publisher","unstructured":"Marx, D., Wollan, P.: An exact characterization of tractable demand patterns for maximum disjoint path problems. In: Indyk, P. (ed.) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4\u20136, 2015, pp. 642\u2013661. SIAM (2015). https:\/\/doi.org\/10.1137\/1.9781611973730.44","DOI":"10.1137\/1.9781611973730.44"},{"key":"1265_CR38","doi-asserted-by":"publisher","unstructured":"Micali, S., Vazirani, V.V.: An O(sqrt($$\\vert $$v$$\\vert $$) $$\\vert $$E$$\\vert $$) algorithm for finding maximum matching in general graphs. In: 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13\u201315 October 1980, pp. 17\u201327. IEEE Computer Society (1980). https:\/\/doi.org\/10.1109\/SFCS.1980.12","DOI":"10.1109\/SFCS.1980.12"},{"key":"1265_CR39","doi-asserted-by":"crossref","unstructured":"Monien, B.: How to find long paths efficiently. In: Analysis and Design of Algorithms for Combinatorial Problems (Udine, 1982), Volume 109 of North-Holland Mathematics Studies, pp. 239\u2013254. North-Holland, Amsterdam (1985)","DOI":"10.1016\/S0304-0208(08)73110-4"},{"issue":"2","key":"1265_CR40","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1006\/jctb.1993.1035","volume":"58","author":"A Seb\u00f6","year":"1993","unstructured":"Seb\u00f6, A.: General antifactors of graphs. J. Comb. Theory Ser. B 58(2), 174\u2013184 (1993)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"1265_CR41","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1016\/j.jcss.2015.11.008","volume":"82","author":"H Shachnai","year":"2016","unstructured":"Shachnai, H., Zehavi, M.: Representative families: a unified tradeoff-based approach. J. Comput. Syst. Sci. 82(3), 488\u2013502 (2016). https:\/\/doi.org\/10.1016\/j.jcss.2015.11.008","journal-title":"J. Comput. Syst. Sci."},{"key":"1265_CR42","doi-asserted-by":"publisher","unstructured":"van Rooij, J.M.M.: Fast algorithms for join operations on tree decompositions. In: Fomin, F.V., Kratsch, S., van Leeuwen, E.J. (eds.) Treewidth, Kernels, and Algorithms\u2014Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, Volume 12160 of Lecture Notes in Computer Science, pp. 262\u2013297. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-42071-0_18","DOI":"10.1007\/978-3-030-42071-0_18"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01265-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01265-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01265-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T13:24:53Z","timestamp":1737120293000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01265-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,15]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["1265"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01265-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,10,15]]},"assertion":[{"value":"13 January 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflict of interest to declare that are considered relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Conference Version: []. Full Version: [].","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Related Version"}}]}}