乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T05:18:44Z","timestamp":1672636724721},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T00:00:00Z","timestamp":1552608000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council (ERC) via grants Rigorous Theory of Preprocessing","award":["267959"]},{"name":"PARAPPROX","award":["306992"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"\n Given a graph\n G<\/jats:italic>\n and a pair (\n F<\/jats:italic>\n 1<\/jats:sub>\n ,\n F<\/jats:italic>\n 2<\/jats:sub>\n ) of graph families, the function GDISJ\n \n G<\/jats:italic>\n ,\n F<\/jats:italic>\n 1<\/jats:sub>\n ,\n F<\/jats:italic>\n 2<\/jats:sub>\n <\/jats:sub>\n takes as input, two induced subgraphs\n G<\/jats:italic>\n 1<\/jats:sub>\n and\n G<\/jats:italic>\n 2<\/jats:sub>\n of\n G<\/jats:italic>\n , such that\n G<\/jats:italic>\n 1<\/jats:sub>\n \u2208\n F<\/jats:italic>\n 1<\/jats:sub>\n and\n G<\/jats:italic>\n 2<\/jats:sub>\n \u2208\n F<\/jats:italic>\n 2<\/jats:sub>\n and returns 1 if\n V<\/jats:italic>\n (\n G<\/jats:italic>\n 1<\/jats:sub>\n )\u2229\n V<\/jats:italic>\n (\n G<\/jats:italic>\n 2<\/jats:sub>\n )=\u2205 and 0 otherwise. We study the communication complexity of this problem in the two-party model. In particular, we look at pairs of hereditary graph families. We show that the communication complexity of this function, when the two graph families are hereditary, is sublinear if and only if there are finitely many graphs in the intersection of these two families. Then, using concepts from parameterized complexity, we obtain nuanced upper bounds on the communication complexity of GDISJ\n \n G<\/jats:italic>\n ,\n F<\/jats:italic>\n 1<\/jats:sub>\n ,\n F<\/jats:italic>\n 2<\/jats:sub>\n <\/jats:sub>\n . A concept related to communication protocols is that of a (\n F<\/jats:italic>\n 1<\/jats:sub>\n ,\n F<\/jats:italic>\n 2<\/jats:sub>\n )-separating family of a graph\n G<\/jats:italic>\n . A collection\n F<\/jats:italic>\n of subsets of\n V<\/jats:italic>\n (\n G<\/jats:italic>\n ) is called a (\n F<\/jats:italic>\n 1<\/jats:sub>\n ,\n F<\/jats:italic>\n 2<\/jats:sub>\n )-\n separating family<\/jats:italic>\n for\n G<\/jats:italic>\n , if for any two vertex disjoint induced subgraphs\n G<\/jats:italic>\n 1<\/jats:sub>\n \u2208\n F<\/jats:italic>\n 1<\/jats:sub>\n ,\n G<\/jats:italic>\n 2<\/jats:sub>\n \u2208\n F<\/jats:italic>\n 2<\/jats:sub>\n , there is a set\n F<\/jats:italic>\n \u2208\n F<\/jats:italic>\n with\n V<\/jats:italic>\n (\n G<\/jats:italic>\n 1<\/jats:sub>\n ) \u2286\n F<\/jats:italic>\n and\n V<\/jats:italic>\n (\n G<\/jats:italic>\n 2<\/jats:sub>\n ) \u2229\n F<\/jats:italic>\n = \u2205. Given a graph\n G<\/jats:italic>\n on\n n<\/jats:italic>\n vertices, for any pair (\n F<\/jats:italic>\n 1<\/jats:sub>\n ,\n F<\/jats:italic>\n 2<\/jats:sub>\n ) of hereditary graph families with sublinear communication complexity for GDISJ\n \n G<\/jats:italic>\n ,\n F<\/jats:italic>\n 1<\/jats:sub>\n ,\n F<\/jats:italic>\n 2<\/jats:sub>\n <\/jats:sub>\n , we give an enumeration algorithm that finds a subexponential sized (\n F<\/jats:italic>\n 1<\/jats:sub>\n ,\n F<\/jats:italic>\n 2<\/jats:sub>\n )-separating family. In fact, we give an enumeration algorithm that finds a 2\n \n o<\/jats:italic>\n (\n k<\/jats:italic>\n )\n <\/jats:sup>\n n<\/jats:italic>\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n sized (\n F<\/jats:italic>\n 1<\/jats:sub>\n ,\n F<\/jats:italic>\n 2<\/jats:sub>\n )-separating family, where\n k<\/jats:italic>\n denotes the size of a minimum sized set\n S<\/jats:italic>\n of vertices such that\n V<\/jats:italic>\n (\n G<\/jats:italic>\n )\\\n S<\/jats:italic>\n has a bipartition (\n V<\/jats:italic>\n 1<\/jats:sub>\n ,\n V<\/jats:italic>\n 2<\/jats:sub>\n ) with\n G<\/jats:italic>\n [\n V<\/jats:italic>\n 1<\/jats:sub>\n ] \u2208\n F<\/jats:italic>\n 1<\/jats:sub>\n and\n G<\/jats:italic>\n [\n V<\/jats:italic>\n 2<\/jats:sub>\n ]\u2208\n F<\/jats:italic>\n 2<\/jats:sub>\n . We exhibit a wide range of applications for these separating families, to obtain combinatorial bounds, enumeration algorithms, as well as exact and FPT algorithms for several problems.\n <\/jats:p>","DOI":"10.1145\/3313234","type":"journal-article","created":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T12:13:05Z","timestamp":1552651985000},"page":"1-28","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Communication Complexity and Graph Families"],"prefix":"10.1145","volume":"11","author":[{"given":"Sudeshna","family":"Kolay","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Netherlands"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[{"name":"University of Bergen, Norway"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, Chennai, India"}]}],"member":"320","published-online":{"date-parts":[[2019,3,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2747014.2747167"},{"key":"e_1_2_1_2_1","volume-title":"Parameterized complexity dichotomy for (r, l)-vertex deletion. CoRR abs\/1504.05515","author":"Baste Julien","year":"2015","unstructured":"Julien Baste , Luerbio Faria , Sulamita Klein , and Ignasi Sau . 2015. Parameterized complexity dichotomy for (r, l)-vertex deletion. CoRR abs\/1504.05515 ( 2015 ). http:\/\/arxiv.org\/abs\/1504.05515 Julien Baste, Luerbio Faria, Sulamita Klein, and Ignasi Sau. 2015. Parameterized complexity dichotomy for (r, l)-vertex deletion. CoRR abs\/1504.05515 (2015). http:\/\/arxiv.org\/abs\/1504.05515"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2014.02.003"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.026"},{"key":"e_1_2_1_6_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.01.001"},{"key":"e_1_2_1_8_1","volume-title":"Graph Theory","author":"Diestel R.","unstructured":"R. Diestel . 2000. Graph Theory ( 2 nd ed., electronic ed.). Springer , Berlin . R. Diestel. 2000. Graph Theory (2nd ed., electronic ed.). Springer, Berlin.","edition":"2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301373"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1409020.1409030"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.62"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.69"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3170711"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.70"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-003-1158-7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/09077850X"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2746-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634204"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.05.001"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS\u201915)","author":"Kolay Sudeshna","year":"2015","unstructured":"Sudeshna Kolay and Fahad Panolan . 2015 . Parameterized algorithms for deletion to (r,l)-graphs . In Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS\u201915) . 420--433. Sudeshna Kolay and Fahad Panolan. 2015. Parameterized algorithms for deletion to (r,l)-graphs. In Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS\u201915). 420--433."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201917)","author":"Kolay Sudeshna","year":"2017","unstructured":"Sudeshna Kolay , Fahad Panolan , and Saket Saurabh . 2017 . Communication complexity of pairs of graph families with applications . In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201917) . 13:1--13:13. Sudeshna Kolay, Fahad Panolan, and Saket Saurabh. 2017. Communication complexity of pairs of graph families with applications. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201917). 13:1--13:13."},{"key":"e_1_2_1_22_1","volume-title":"Communication Complexity","author":"Kushilevitz Eyal","unstructured":"Eyal Kushilevitz and Noam Nisan . 1997. Communication Complexity . Cambridge University Press , New York . Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press, New York."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566616"},{"key":"e_1_2_1_24_1","volume-title":"Communication complexity: A survey. Paths, flows, and VLSI-layout","author":"Lov\u00e1sz L\u00e1szl\u00f3","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz . 1990. Communication complexity: A survey. Paths, flows, and VLSI-layout . Princeton University Press , 235--265. L\u00e1szl\u00f3 Lov\u00e1sz. 1990. Communication complexity: A survey. Paths, flows, and VLSI-layout. Princeton University Press, 235--265."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)00057-X"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760024"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00009-1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33293-7_3"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.10.029"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90024-Y"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313234","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T10:22:42Z","timestamp":1672568562000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313234"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,15]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3313234"],"URL":"https:\/\/doi.org\/10.1145\/3313234","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,15]]},"assertion":[{"value":"2017-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}