{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T09:04:56Z","timestamp":1777539896220,"version":"3.51.4"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,3,13]],"date-time":"2017-03-13T00:00:00Z","timestamp":1489363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Rigorous Theory of Preprocessing, ERC Advanced Investigator","award":["267959"],"award-info":[{"award-number":["267959"]}]},{"name":"Parameterized Approximation, ERC Starting","award":["306992"],"award-info":[{"award-number":["306992"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,7,31]]},"abstract":"<jats:p>\n            A subfamily\n            <jats:italic>F\u2032<\/jats:italic>\n            of a set family\n            <jats:italic>F<\/jats:italic>\n            is said to\n            <jats:italic>q<\/jats:italic>\n            -\n            <jats:italic>represent<\/jats:italic>\n            <jats:italic>F<\/jats:italic>\n            if for every\n            <jats:italic>A<\/jats:italic>\n            \u2208\n            <jats:italic>F<\/jats:italic>\n            and\n            <jats:italic>B<\/jats:italic>\n            of size\n            <jats:italic>q<\/jats:italic>\n            such that\n            <jats:italic>A<\/jats:italic>\n            \u2229\n            <jats:italic>B<\/jats:italic>\n            = \u2205 there exists a set\n            <jats:italic>A\u2032<\/jats:italic>\n            \u2208\n            <jats:italic>F\u2032<\/jats:italic>\n            such that\n            <jats:italic>A\u2032<\/jats:italic>\n            \u2229\n            <jats:italic>B<\/jats:italic>\n            = \u2205. Recently, we provided an algorithm that, for a given family\n            <jats:italic>F<\/jats:italic>\n            of sets of size\n            <jats:italic>p<\/jats:italic>\n            together with an integer\n            <jats:italic>q<\/jats:italic>\n            , efficiently computes a\n            <jats:italic>q<\/jats:italic>\n            -representative family\n            <jats:italic>F\u2032<\/jats:italic>\n            of\n            <jats:italic>F<\/jats:italic>\n            of size approximately (p+q p). In this article, we consider the efficient computation of\n            <jats:italic>q<\/jats:italic>\n            -representative families for\n            <jats:italic>product<\/jats:italic>\n            families\n            <jats:italic>F<\/jats:italic>\n            . A family\n            <jats:italic>F<\/jats:italic>\n            is a product family if there exist families\n            <jats:italic>A<\/jats:italic>\n            and\n            <jats:italic>B<\/jats:italic>\n            such that\n            <jats:italic>F<\/jats:italic>\n            = {\n            <jats:italic>A<\/jats:italic>\n            , \u222a,\n            <jats:italic>B<\/jats:italic>\n            :\n            <jats:italic>A<\/jats:italic>\n            \u2208\n            <jats:italic>A<\/jats:italic>\n            ,\n            <jats:italic>B<\/jats:italic>\n            \u2208\n            <jats:italic>B<\/jats:italic>\n            ,\n            <jats:italic>A<\/jats:italic>\n            , \u2229,\n            <jats:italic>B<\/jats:italic>\n            = \u2205}. Our main technical contribution is an algorithm that, given\n            <jats:italic>A<\/jats:italic>\n            ,\n            <jats:italic>B<\/jats:italic>\n            and\n            <jats:italic>q<\/jats:italic>\n            , computes a\n            <jats:italic>q<\/jats:italic>\n            -representative family\n            <jats:italic>F\u2032<\/jats:italic>\n            of\n            <jats:italic>F<\/jats:italic>\n            . The running time of our algorithm is\n            <jats:italic>sublinear<\/jats:italic>\n            in |\n            <jats:italic>F<\/jats:italic>\n            | for many choices of\n            <jats:italic>A<\/jats:italic>\n            ,\n            <jats:italic>B<\/jats:italic>\n            , and\n            <jats:italic>q<\/jats:italic>\n            that occur naturally in several dynamic programming algorithms. We also give an algorithm for the computation of\n            <jats:italic>q<\/jats:italic>\n            -representative families for product families\n            <jats:italic>F<\/jats:italic>\n            in the more general setting where\n            <jats:italic>q<\/jats:italic>\n            -representation also involves independence in a matroid in addition to disjointness. This algorithm considerably outperforms the naive approach where one first computes\n            <jats:italic>F<\/jats:italic>\n            from\n            <jats:italic>A<\/jats:italic>\n            and\n            <jats:italic>B<\/jats:italic>\n            and then computes the\n            <jats:italic>q<\/jats:italic>\n            -representative family\n            <jats:italic>F\u2032<\/jats:italic>\n            from\n            <jats:italic>F<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            We give two applications of our new algorithms for computing\n            <jats:italic>q<\/jats:italic>\n            -representative families for product families. The first is a 3.8408\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            deterministic algorithm for the M\n            <jats:sc>ultilinear<\/jats:sc>\n            M\n            <jats:sc>onomial<\/jats:sc>\n            D\n            <jats:sc>etection<\/jats:sc>\n            (\n            <jats:italic>k<\/jats:italic>\n            -M\n            <jats:sc>l<\/jats:sc>\n            D) problem. The second is a significant improvement of deterministic dynamic programming algorithms for \u201cconnectivity problems\u201d on graphs of bounded treewidth.\n          <\/jats:p>","DOI":"10.1145\/3039243","type":"journal-article","created":{"date-parts":[[2017,3,15]],"date-time":"2017-03-15T14:18:04Z","timestamp":1489587484000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Representative Families of Product Families"],"prefix":"10.1145","volume":"13","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, HBNI, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, HBNI, Chennai, India and University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,3,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0110042"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1962-10802-7"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC","author":"Bj\u00f6rklund Andreas","year":"2007","unstructured":"Andreas Bj\u00f6rklund , Thore Husfeldt , Petteri Kaski , and Mikko Koivisto . 2007 . Fourier meets m\u00f6bious: Fast subset convolution . In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007). ACM Press, New York, NY. Andreas Bj\u00f6rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. 2007. Fourier meets m\u00f6bious: Fast subset convolution. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007). ACM Press, New York, NY."},{"key":"e_1_2_1_5_1","volume-title":"Narrow sieves for parameterized paths and packings. CoRR abs\/1007.1161","author":"Bj\u00f6rklund Andreas","year":"2010","unstructured":"Andreas Bj\u00f6rklund , Thore Husfeldt , Petteri Kaski , and Mikko Koivisto . 2010. Narrow sieves for parameterized paths and packings. CoRR abs\/1007.1161 ( 2010 ). Andreas Bj\u00f6rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. 2010. Narrow sieves for parameterized paths and packings. CoRR abs\/1007.1161 (2010)."},{"key":"e_1_2_1_6_1","first-page":"20","article-title":"Probably optimal graph motifs","volume":"20","author":"Bj\u00f6rklund Andreas","year":"2013","unstructured":"Andreas Bj\u00f6rklund , Petteri Kaski , and Lukasz Kowalik . 2013 . Probably optimal graph motifs . In STACS (LIPIcs) , Vol. 20. 20 -- 31 . Andreas Bj\u00f6rklund, Petteri Kaski, and Lukasz Kowalik. 2013. Probably optimal graph motifs. In STACS (LIPIcs), Vol. 20. 20--31.","journal-title":"STACS (LIPIcs)"},{"key":"e_1_2_1_7_1","volume-title":"ICALP. CoRR","author":"Bodlaender Hans L.","year":"2013","unstructured":"Hans L. Bodlaender , Marek Cygan , Stefan Kratsch , and Jesper Nederlof . 2013. Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time , In ICALP. CoRR ( 2013 ), 196--207. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. 2013. Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time, In ICALP. CoRR (2013), 196--207."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.10.001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.10"},{"key":"e_1_2_1_13_1","volume-title":"Powers of tensors and fast matrix multiplication. CoRR abs\/1401.7714","author":"Gall Fran\u00e7ois Le","year":"2014","unstructured":"Fran\u00e7ois Le Gall . 2014. Powers of tensors and fast matrix multiplication. CoRR abs\/1401.7714 ( 2014 ). http:\/\/arxiv.org\/abs\/1401.7714 Fran\u00e7ois Le Gall. 2014. Powers of tensors and fast matrix multiplication. CoRR abs\/1401.7714 (2014). http:\/\/arxiv.org\/abs\/1401.7714"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9600-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17364-6"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_47"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.08.008"},{"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":"publisher","DOI":"10.1145\/2742544"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_75"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Sixth British Combinatorial Conference. Academic Press","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1977","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz . 1977 . Flats in matroids and geometric graphs. In Combinatorial Surveys , Proceedings of the Sixth British Combinatorial Conference. Academic Press , London, 45--86. L\u00e1szl\u00f3 Lov\u00e1sz. 1977. Flats in matroids and geometric graphs. In Combinatorial Surveys, Proceedings of the Sixth British Combinatorial Conference. Academic Press, London, 45--86."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.008"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.027"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73110-4"},{"key":"e_1_2_1_26_1","volume-title":"Matroid Theory","author":"Oxley James G.","unstructured":"James G. Oxley . 2006. Matroid Theory . Vol. 3 . Oxford University Press . James G. Oxley. 2006. Matroid Theory. Vol. 3. Oxford University Press."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201916)","author":"Panolan Fahad","year":"2016","unstructured":"Fahad Panolan and Meirav Zehavi . 2016 . Parameterized algorithms for list k-cycle . In Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201916) . 22:1--22:15. http:\/\/dx.doi.org\/10.4230\/LIPIcs.FSTTCS.2016.22 10.4230\/LIPIcs.FSTTCS.2016.22 Fahad Panolan and Meirav Zehavi. 2016. Parameterized algorithms for list k-cycle. In Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201916). 22:1--22:15. http:\/\/dx.doi.org\/10.4230\/LIPIcs.FSTTCS.2016.22"},{"key":"e_1_2_1_28_1","volume-title":"Extremal Problems for Finite Sets (Visegr\u00e1d","volume":"3","author":"Tuza Zsolt","year":"1994","unstructured":"Zsolt Tuza . 1994 . Applications of the set-pair method in extremal hypergraph theory . In Extremal Problems for Finite Sets (Visegr\u00e1d , 1991). Bolyai Soc. Math. Stud. , Vol. 3 . J\u00e1nos Bolyai Math. Soc., Budapest, 479--514. Zsolt Tuza. 1994. Applications of the set-pair method in extremal hypergraph theory. In Extremal Problems for Finite Sets (Visegr\u00e1d, 1991). Bolyai Soc. Math. Stud., Vol. 3. J\u00e1nos Bolyai Math. Soc., Budapest, 479--514."},{"key":"e_1_2_1_29_1","volume-title":"Paul Erd\u0151s Is Eighty","volume":"2","author":"Tuza Zsolt","year":"1996","unstructured":"Zsolt Tuza . 1996 . Applications of the set-pair method in extremal problems. ii. In Combinatorics , Paul Erd\u0151s Is Eighty , Vol. 2 (Keszthely, 1993). Bolyai Soc. Math. Stud. , Vol. 2. J\u00e1nos Bolyai Math. Soc., Budapest, 459--490. Zsolt Tuza. 1996. Applications of the set-pair method in extremal problems. ii. In Combinatorics, Paul Erd\u0151s Is Eighty, Vol. 2 (Keszthely, 1993). Bolyai Soc. Math. Stud., Vol. 2. J\u00e1nos Bolyai Math. Soc., Budapest, 459--490."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.11.004"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3039243","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3039243","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:30Z","timestamp":1750217790000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3039243"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,13]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7,31]]}},"alternative-id":["10.1145\/3039243"],"URL":"https:\/\/doi.org\/10.1145\/3039243","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,13]]},"assertion":[{"value":"2016-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}