{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:11:50Z","timestamp":1787508710044,"version":"build-2736575974"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,4,25]],"date-time":"2016-04-25T00:00:00Z","timestamp":1461542400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Simons Foundation, and NSF","award":["1319051 and CCF-121351"],"award-info":[{"award-number":["1319051 and CCF-121351"]}]},{"name":"Government of the Russian Federation","award":["14.Z50.31.0030"],"award-info":[{"award-number":["14.Z50.31.0030"]}]},{"name":"President of the Russian Federation","award":["MK-6550.2015.1"],"award-info":[{"award-number":["MK-6550.2015.1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,6,15]]},"abstract":"<jats:p>\n                    Assume that a group of\n                    <jats:italic>n<\/jats:italic>\n                    people is going to an excursion and our task is to seat them into buses with several constraints each saying that a pair of people does not want to see each other in the same bus. This is a well-known graph coloring problem (with\n                    <jats:italic>n<\/jats:italic>\n                    being the number of vertices) and it can be solved in\n                    <jats:italic>O<\/jats:italic>\n                    *(2\n                    <jats:sup>\n                      <jats:italic>n<\/jats:italic>\n                    <\/jats:sup>\n                    ) time by the inclusion-exclusion principle as shown by Bj\u00f6rklund, Husfeldt, and Koivisto in 2009. Another approach to solve this problem in\n                    <jats:italic>O<\/jats:italic>\n                    *(2\n                    <jats:sup>\n                      <jats:italic>n<\/jats:italic>\n                    <\/jats:sup>\n                    ) time is to use the Fast Fourier Transform (FFT). For this, given a graph\n                    <jats:italic>G<\/jats:italic>\n                    one constructs a polynomial\n                    <jats:italic>\n                      P\n                      <jats:sub>G<\/jats:sub>\n                    <\/jats:italic>\n                    (\n                    <jats:italic>x<\/jats:italic>\n                    ) of degree\n                    <jats:italic>O<\/jats:italic>\n                    *(2\n                    <jats:sup>\n                      <jats:italic>n<\/jats:italic>\n                    <\/jats:sup>\n                    ) with the following property:\n                    <jats:italic>G<\/jats:italic>\n                    is\n                    <jats:italic>k<\/jats:italic>\n                    -colorable if and only if the coefficient of\n                    <jats:italic>\n                      x\n                      <jats:sup>m<\/jats:sup>\n                    <\/jats:italic>\n                    (for some particular value of\n                    <jats:italic>m<\/jats:italic>\n                    ) in the\n                    <jats:italic>k<\/jats:italic>\n                    -th power of\n                    <jats:italic>P<\/jats:italic>\n                    (\n                    <jats:italic>x<\/jats:italic>\n                    ) is nonzero. Then, it remains to compute this coefficient using FFT.\n                  <\/jats:p>\n                  <jats:p>\n                    Assume now that we have additional constraints: the group of people contains several infants and these infants should be accompanied by their relatives in a bus. We show that if the number of infants is linear, then the problem can be solved in\n                    <jats:italic>O<\/jats:italic>\n                    *((2 \u2212 \u03b5)\n                    <jats:sup>\n                      <jats:italic>n<\/jats:italic>\n                    <\/jats:sup>\n                    ) time, where \u03b5 is a positive constant independent of\n                    <jats:italic>n<\/jats:italic>\n                    . We use this approach to improve known bounds for several NP-hard problems (the traveling salesman problem, the graph coloring problem, the problem of counting perfect matchings) on graphs of bounded average degree, as well as to simplify the proofs of several known results.\n                  <\/jats:p>","DOI":"10.1145\/2847419","type":"journal-article","created":{"date-parts":[[2016,4,25]],"date-time":"2016-04-25T15:51:13Z","timestamp":1461599473000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Families with Infants"],"prefix":"10.1145","volume":"12","author":[{"given":"Alexander","family":"Golovnev","sequence":"first","affiliation":[{"name":"New York University, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander S.","family":"Kulikov","sequence":"additional","affiliation":[{"name":"St. Petersburg Department of Steklov Institute of Mathematics of the Russian Academy of Sciences, St. Petersburg, Russia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ivan","family":"Mihajlin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California, San Diego, La Jolla, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,4,25]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"PRIMES is in P. Annals of Mathematics","author":"Agrawal Manindra","year":"2004","unstructured":"Manindra Agrawal , Neeraj Kayal , and Nitin Saxena . 2004. PRIMES is in P. Annals of Mathematics ( 2004 ), 781--793. Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. 2004. PRIMES is in P. Annals of Mathematics (2004), 781--793."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0072-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321111"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.24"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095189"},{"key":"e_1_2_1_7_1","volume-title":"Narrow sieves for parameterized paths and packings. arXiv:1007.1161","author":"Bj\u00f6rklund Andreas","year":"2010","unstructured":"Andreas Bj\u00f6rklund , Thore Husfeldt , Petteri Kaski , and Mikko Koivisto . 2010a. Narrow sieves for parameterized paths and packings. arXiv:1007.1161 ( 2010 ). Andreas Bj\u00f6rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. 2010a. Narrow sieves for parameterized paths and packings. arXiv:1007.1161 (2010)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9185-7"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2151171.2151181"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683933"},{"key":"e_1_2_1_11_1","volume-title":"Introduction to Algorithms, (3rd. ed.)","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms, (3rd. ed.) . MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, (3rd. ed.). MIT Press."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488646"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.018"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_31"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.69"},{"key":"e_1_2_1_16_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP","author":"Golovnev Alexander","year":"2014","unstructured":"Alexander Golovnev , Aleaxnder S. Kulikov , and Ivan Mihajlin . 2014. Families with infants: A general approach to solve hard partition problems . In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014 ), Lecture Notes in Computer Science , Vol. 8572 . Springer , Berlin , 551--562. Alexander Golovnev, Aleaxnder S. Kulikov, and Ivan Mihajlin. 2014. Families with infants: A general approach to solve hard partition problems. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), Lecture Notes in Computer Science, Vol. 8572. Springer, Berlin, 551--562."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0110015"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.28"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_54"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1515\/crll.1882.92.1","article-title":"Grundz\u00fcge einer arithmetischen theorie der algebraischen Gr\u00f6ssen","volume":"92","author":"Kronecker Leopold","year":"1882","unstructured":"Leopold Kronecker . 1882 . Grundz\u00fcge einer arithmetischen theorie der algebraischen Gr\u00f6ssen . Journal f\u00fcr die reine und angewandte Mathematik 92 (1882), 1 -- 122 . Leopold Kronecker. 1882. Grundz\u00fcge einer arithmetischen theorie der algebraischen Gr\u00f6ssen. Journal f\u00fcr die reine und angewandte Mathematik 92 (1882), 1--122.","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806735"},{"key":"e_1_2_1_22_1","volume-title":"Algorithms\u2014ESA","author":"Rooij Johan M. M.","year":"2009","unstructured":"Johan M. M. Rooij , Hans L. Bodlaender , and Peter Rossmanith . 2009. Dynamic programming on tree decompositions using generalised fast subset convolution . In Algorithms\u2014ESA 2009 , Amos Fiat and Peter Sanders (Eds.). Lecture Notes in Computer Science, Vol. 5757 . Springer , Berlin, 566--577. Johan M. M. Rooij, Hans L. Bodlaender, and Peter Rossmanith. 2009. Dynamic programming on tree decompositions using generalised fast subset convolution. In Algorithms\u2014ESA 2009, Amos Fiat and Peter Sanders (Eds.). Lecture Notes in Computer Science, Vol. 5757. Springer, Berlin, 566--577."},{"key":"e_1_2_1_23_1","volume-title":"Combinatorial Mathematics","author":"Ryser Herbert John","unstructured":"Herbert John Ryser . 1963. Combinatorial Mathematics . Mathematical Association of America, Washington , DC. Herbert John Ryser. 1963. Combinatorial Mathematics. Mathematical Association of America, Washington, DC."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.06.007"},{"key":"e_1_2_1_25_1","volume-title":"A Computational Introduction to Number Theory and Algebra (2nd. ed.)","author":"Shoup Victor","unstructured":"Victor Shoup . 2009. A Computational Introduction to Number Theory and Algebra (2nd. ed.) . Cambridge University Press . Victor Shoup. 2009. A Computational Introduction to Number Theory and Algebra (2nd. ed.). Cambridge University Press."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2847419","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2847419","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:43:26Z","timestamp":1750211006000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2847419"}},"subtitle":["Speeding Up Algorithms for NP-Hard Problems Using FFT"],"short-title":[],"issued":{"date-parts":[[2016,4,25]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6,15]]}},"alternative-id":["10.1145\/2847419"],"URL":"https:\/\/doi.org\/10.1145\/2847419","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,25]]},"assertion":[{"value":"2014-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}