{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:02Z","timestamp":1740109322396,"version":"3.37.3"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T00:00:00Z","timestamp":1649030400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T00:00:00Z","timestamp":1649030400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006764","name":"Technische Universit\u00e4t Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006764","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In <jats:sc>Directed Feedback Arc Set<\/jats:sc> (<jats:sc>DFAS<\/jats:sc>) we search for a set of at most <jats:italic>k<\/jats:italic> arcs which intersect every cycle in the input digraph. It is a well-known open problem in parameterized complexity to decide if <jats:sc>DFAS<\/jats:sc> admits a kernel of polynomial size. We consider <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {C}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>C<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-<jats:sc>Arc Deletion Set<\/jats:sc> (<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {C}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>C<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-<jats:sc>ADS<\/jats:sc>), a variant of <jats:sc>DFAS<\/jats:sc> where we want to remove at most <jats:italic>k<\/jats:italic> arcs from the input digraph in order to turn it into a digraph of a class <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {C}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>C<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In this work, we choose <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {C}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>C<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> to be the class of <jats:italic>funnels<\/jats:italic>. <jats:sc>Funnel<\/jats:sc>-<jats:sc>ADS<\/jats:sc> is NP-hard even if the input is a DAG, but is fixed-parameter tractable with respect to <jats:italic>k<\/jats:italic>. So far no polynomial kernels for this problem were known. Our main result is a kernel for <jats:sc>Funnel<\/jats:sc>-<jats:sc>ADS<\/jats:sc> with <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O}(k^6)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mn>6<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> many vertices and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O}(k^7)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mn>7<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> many arcs, computable in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O}(nm)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, where <jats:italic>n<\/jats:italic> is the number of vertices and <jats:italic>m<\/jats:italic> the number of arcs in the input digraph.\n<\/jats:p>","DOI":"10.1007\/s00453-022-00960-w","type":"journal-article","created":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T15:02:58Z","timestamp":1649084578000},"page":"2358-2378","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Polynomial Kernel for Funnel Arc Deletion Set"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8398-4751","authenticated-orcid":false,"given":"Marcelo","family":"Garlet Milani","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,4]]},"reference":[{"key":"960_CR1","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, \u0141, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, vol. 5. Springer, Cham (2015)"},{"key":"960_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity, vol. 4. Springer, London (2013)"},{"issue":"5","key":"960_CR3","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/1411509.1411511","volume":"55","author":"J Chen","year":"2008","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5), 21 (2008)","journal-title":"J. ACM"},{"issue":"7","key":"960_CR4","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1016\/j.jcss.2009.09.002","volume":"76","author":"FN Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: A kernelization algorithm for $$d$$-hitting set. J. Comput. Syst. Sci. 76(7), 524\u2013531 (2010)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"960_CR5","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/s00453-015-0038-2","volume":"76","author":"J Bang-Jensen","year":"2016","unstructured":"Bang-Jensen, J., Maddaloni, A., Saurabh, S.: Algorithms and kernels for feedback set problems in generalizations of tournaments. Algorithmica 76(2), 320\u2013343 (2016)","journal-title":"Algorithmica"},{"key":"960_CR6","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Ramanujan, M., Saurabh, S., Sharma, R., Zehavi, M.: Wannabe bounded treewidth graphs admit a polynomial kernel for dfvs. In: Workshop on Algorithms and Data Structures, pp. 523\u2013537 (2019). Springer","DOI":"10.1007\/978-3-030-24766-9_38"},{"key":"960_CR7","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.disopt.2017.02.002","volume":"25","author":"M Mnich","year":"2017","unstructured":"Mnich, M., van Leeuwen, E.J.: Polynomial kernels for deletion to classes of acyclic digraphs. Discrete Optim. 25, 48\u201376 (2017)","journal-title":"Discrete Optim."},{"key":"960_CR8","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.jcss.2017.07.008","volume":"92","author":"A Agrawal","year":"2018","unstructured":"Agrawal, A., Saurabh, S., Sharma, R., Zehavi, M.: Kernels for deletion to classes of acyclic digraphs. J. Comput. Syst. Sci. 92, 9\u201321 (2018)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"960_CR9","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/s10878-019-00464-4","volume":"39","author":"M Garlet Millani","year":"2020","unstructured":"Garlet Millani, M., Molter, H., Niedermeier, R., Sorge, M.: Efficient algorithms for measuring the funnel-likeness of dags. J. Combin. Optim. 39(1), 216\u2013245 (2020)","journal-title":"J. Combin. Optim."},{"key":"960_CR10","unstructured":"Kratsch, S.: Recent developments in kernelization: a survey. Bull. EATCS 2(113) (2014)"},{"key":"960_CR11","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Misra, N., Saurabh, S.: Kernelization\u2014preprocessing with a guarantee. In: The Multivariate Algorithmic Revolution and Beyond, pp. 129\u2013161. Springer, Berlin, Heidelberg (2012)","DOI":"10.1007\/978-3-642-30891-8_10"},{"key":"960_CR12","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, United Kingdom (2019)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00960-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00960-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00960-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T13:10:52Z","timestamp":1658409052000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00960-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,4]]},"references-count":12,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["960"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00960-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,4,4]]},"assertion":[{"value":"18 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}