{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:02:49Z","timestamp":1750309369375,"version":"3.41.0"},"reference-count":9,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T00:00:00Z","timestamp":1725840000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Science\/Mathematics Summer Undergraduate Research Fellowship Fund at CCS"},{"name":"2022 Summer Undergraduate Research Fellowship"},{"name":"Computer Science Endowment at CCS"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"\n An\n independent set<\/jats:italic>\n in a graph\n G<\/jats:italic>\n is a set\n S<\/jats:italic>\n of pairwise non-adjacent vertices in\n G<\/jats:italic>\n . A family\n \n \\(\\mathcal {F}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of independent sets in\n G<\/jats:italic>\n is called a\n k<\/jats:italic>\n -\n independence covering family<\/jats:italic>\n if for every independent set\n I<\/jats:italic>\n in\n G<\/jats:italic>\n of size at most\n k<\/jats:italic>\n , there exists an\n \n \\(S \\in \\mathcal {F}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n such that\n \n \\(I \\subseteq S\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Lokshtanov et\u00a0al.\n (ACM Transactions on Algorithms<\/jats:italic>\n , 2020) showed that graphs of degeneracy\n d<\/jats:italic>\n admit\n k<\/jats:italic>\n -independence covering families of size\n \n \\(\\binom{k(d+1)}{k} \\cdot 2^{o(kd)} \\cdot \\log n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and used this result to design efficient parameterized algorithms for a number of problems, including\n Stable Odd Cycle Transversal<\/jats:sc>\n and\n Stable Multicut<\/jats:sc>\n .\n <\/jats:p>\n \n In light of the results of Lokshtanov et\u00a0al.\n (ACM Transactions on Algorithms,<\/jats:italic>\n 2020) it is quite natural to ask whether even more general families of graphs admit\n k<\/jats:italic>\n -independence covering families of size\n \n \\(f(k)n^{O(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Graphs that exclude a complete bipartite graph\n \n \\(K_{d+1,d+1}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n with\n \n \\(d+1\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n vertices on both sides as a subgraph, called\n \n \\(K_{d+1,d+1}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -\n free graphs<\/jats:italic>\n , are a frequently considered generalization of\n d<\/jats:italic>\n -degenerate graphs. This motivates the question of whether\n \n \\(K_{d,d}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -free graphs admit\n k<\/jats:italic>\n -independence covering families of size\n \n \\(f(k,d)n^{O(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Our main result is a resounding \u201cno\u201d to this question\u2014specifically, we prove that even\n \n \\(K_{2,2}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -free graphs (or equivalently\n \n \\(C_4\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -free graphs) do not admit\n k<\/jats:italic>\n -independence covering families of size\n \n \\(f(k)n^{\\frac{k}{4}-\\epsilon }\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>","DOI":"10.1145\/3664277","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T07:27:48Z","timestamp":1717054068000},"page":"1-7","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Lower Bound for Independence Covering in\n C<\/i>\n 4<\/sub>\n -free Graphs"],"prefix":"10.1145","volume":"16","author":[{"given":"Michael","family":"Kuhn","sequence":"first","affiliation":[{"name":"University of California Santa Barbara, Santa Barbara, United States"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of California Santa Barbara, Santa Barbara, United States"}]},{"given":"Zachary","family":"Miller","sequence":"additional","affiliation":[{"name":"University of California Santa Barbara, Santa Barbara, United States"}]}],"member":"320","published-online":{"date-parts":[[2024,9,9]]},"reference":[{"key":"e_1_3_1_2_2","series-title":"LIPIcs","first-page":"39:1\u201339:14","volume-title":"33rd International Symposium on Algorithms and Computation (ISAAC\u201922)","author":"Agrawal Akanksha","year":"2022","unstructured":"Akanksha Agrawal, Soumita Hait, and Amer E. Mouawad. 2022. On finding short reconfiguration sequences between independent sets. In 33rd International Symposium on Algorithms and Computation (ISAAC\u201922)(LIPIcs, Vol. 248), Sang Won Bae and Heejin Park (Eds.). Dagstuhl Publishing, Wadern, Germany, 39:1\u201339:14."},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00681-y"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-01-00934-X"},{"key":"e_1_3_1_5_2","article-title":"On solution discovery via reconfiguration","volume":"2304","author":"Fellows Michael R.","year":"2023","unstructured":"Michael R. Fellows, Mario Grobler, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi, Frances A. Rosamond, Daniel Schmand, and Sebastian Siebertz. 2023. On solution discovery via reconfiguration. CoRR abs\/2304.14295 (2023).","journal-title":"CoRR"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-020-10022-9"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-019-09964-6"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/2090021"},{"issue":"3","key":"e_1_3_1_9_2","first-page":"31","article-title":"Covering small independent sets and separators with applications to parameterized algorithms","volume":"16","author":"Lokshtanov Daniel","year":"2020","unstructured":"Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. 2020. Covering small independent sets and separators with applications to parameterized algorithms. ACM Trans. Algor. 16, 3 (2020), 31 pages.","journal-title":"ACM Trans. Algor."},{"issue":"3","key":"e_1_3_1_10_2","first-page":"15","article-title":"The isoperimetric number of the incidence graph of PG(n,q)","volume":"25","author":"Price Andrew Elvey","year":"2018","unstructured":"Andrew Elvey Price, Muhammad Adib Surani, and Sanming Zhou. 2018. The isoperimetric number of the incidence graph of PG(n,q). Electron. J. Combinatorics 25, 3 (2018), 15 pages.","journal-title":"Electron. J. Combinatorics"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3664277","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3664277","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:06:14Z","timestamp":1750291574000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3664277"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,9]]},"references-count":9,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3664277"],"URL":"https:\/\/doi.org\/10.1145\/3664277","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2024,9,9]]},"assertion":[{"value":"2023-09-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-22","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}