{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:41:59Z","timestamp":1742913719754,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031206238"},{"type":"electronic","value":"9783031206245"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-20624-5_1","type":"book-chapter","created":{"date-parts":[[2022,10,28]],"date-time":"2022-10-28T15:18:05Z","timestamp":1666970285000},"page":"3-19","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Cutting a\u00a0Tree with\u00a0Subgraph Complementation is Hard, Except for\u00a0Some Small Trees"],"prefix":"10.1007","author":[{"given":"Dhanyamol","family":"Antony","sequence":"first","affiliation":[]},{"given":"Sagartanu","family":"Pal","sequence":"additional","affiliation":[]},{"given":"R. B.","family":"Sandeep","sequence":"additional","affiliation":[]},{"given":"R.","family":"Subashini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,29]]},"reference":[{"key":"1_CR1","first-page":"153","volume":"327","author":"M Chudnovsky","year":"2005","unstructured":"Chudnovsky, M., Seymour, P.D.: The structure of claw-free graphs. Surv. Combinat. 327, 153\u2013171 (2005)","journal-title":"Surv. Combinat."},{"issue":"3","key":"1_CR2","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"DG Corneil","year":"1981","unstructured":"Corneil, D.G., Lerchs, H., Stewart Burlingham, L.: Complement reducible graphs. Discret. Appl. Math. 3(3), 163\u2013174 (1981)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"1_CR3","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0020-0190(88)90143-3","volume":"28","author":"S Olariu","year":"1988","unstructured":"Olariu, S.: Paw-fee graphs. Inf. Process. Lett. 28(1), 53\u201354 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"1_CR4","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theo. Ser. B 28(3), 284\u2013304 (1980)","journal-title":"J. Comb. Theo. Ser. B"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Gartland, P., Lokshtanov, D.: Independent set on P$${}_{\\text{k}}$$-free graphs in quasi-polynomial time. In: Irani, S., (ed.) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16\u201319, 2020, pp. 613\u2013624. IEEE (2020)","DOI":"10.1109\/FOCS46700.2020.00063"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Lokshantov, D., Vatshelle, M., Villanger, Y.: Independent set in P$${}_{\\text{5 }}$$-free graphs in polynomial time. In: Chekuri, C., (ed) Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5\u20137, 2014, pp. 570\u2013581. SIAM (2014)","DOI":"10.1137\/1.9781611973402.43"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Pilipczuk, M., Pilipczuk, M., Rz\u0105\u017cewski, P.: Quasi-polynomial-time algorithm for independent set in P$${}_{\\text{ t }}$$-free graphs via shrinking the space of induced paths. In: Viet Le H., King, V., (eds.), 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11\u201312, 2021, pp. 204\u2013209. SIAM (2021)","DOI":"10.1137\/1.9781611976472.23"},{"issue":"1","key":"1_CR8","first-page":"4:1","volume":"18","author":"A Grzesik","year":"2022","unstructured":"Grzesik, A., Klimosov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on P$${}_{\\text{6 }}$$-free graphs. ACM Trans. Algor. 18(1), 4:1-4:57 (2022)","journal-title":"ACM Trans. Algor."},{"issue":"1","key":"1_CR9","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1137\/16M1055797","volume":"31","author":"NR Aravind","year":"2017","unstructured":"Aravind, N.R., Sandeep, R.B., Sivadasan, N.: Dichotomy results on the hardness of H-free edge modification problems. SIAM J. Discret. Math. 31(1), 542\u2013561 (2017)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"1_CR10","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1137\/0210021","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10(2), 297\u2013309 (1981)","journal-title":"SIAM J. Comput."},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-030-86838-3_9","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D Antony","year":"2021","unstructured":"Antony, D., Garchar, J., Pal, S., Sandeep, R.B., Sen, S., Subashini, R.: On subgraph complementation to H-free graphs. In: Kowalik, \u0141, Pilipczuk, M., Rz\u0105\u017cewski, P. (eds.) WG 2021. LNCS, vol. 12911, pp. 118\u2013129. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-86838-3_9"},{"issue":"47\u201349","key":"1_CR12","doi-asserted-by":"publisher","first-page":"4920","DOI":"10.1016\/j.tcs.2009.07.002","volume":"410","author":"N Alon","year":"2009","unstructured":"Alon, N., Stav, U.: Hardness of edge-modification problems. Theor. Comput. Sci. 410(47\u201349), 4920\u20134927 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.endm.2009.02.008","volume":"32","author":"D Br\u00fcgmann","year":"2009","unstructured":"Br\u00fcgmann, D., Komusiewicz, C., Moser, H.: On generating triangle-free graphs. Electron. Notes Discret. Math. 32, 51\u201358 (2009)","journal-title":"Electron. Notes Discret. Math."},{"issue":"3","key":"1_CR14","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1109\/31.1748","volume":"35","author":"ES El-Mallah","year":"1988","unstructured":"El-Mallah, E.S., Colbourn, C.J.: The complexity of some edge deletion problems. IEEE Trans. Circ. Syst. 35(3), 354\u2013362 (1988)","journal-title":"IEEE Trans. Circ. Syst."},{"issue":"15","key":"1_CR15","doi-asserted-by":"publisher","first-page":"2259","DOI":"10.1016\/j.dam.2012.05.019","volume":"160","author":"C Komusiewicz","year":"2012","unstructured":"Komusiewicz, C., Uhlmann, J.: Cluster editing with locally bounded modifications. Discret. Appl. Math. 160(15), 2259\u20132270 (2012)","journal-title":"Discret. Appl. Math."},{"issue":"1\u20132","key":"1_CR16","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.dam.2004.01.007","volume":"144","author":"R Shamir","year":"2004","unstructured":"Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discret. Appl. Math. 144(1\u20132), 173\u2013182 (2004)","journal-title":"Discret. Appl. Math."},{"key":"1_CR17","unstructured":"Sharan, R.: Graph modification problems and their applications to genomic research. PhD thesis, Tel-Aviv University (2002)"},{"issue":"4","key":"1_CR18","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1002\/jgt.21745","volume":"75","author":"E Jel\u00ednkov\u00e1","year":"2014","unstructured":"Jel\u00ednkov\u00e1, E., Kratochv\u00edl, J.: On switching to H-free graphs. J. Graph Theo. 75(4), 387\u2013405 (2014)","journal-title":"J. Graph Theo."},{"issue":"1","key":"1_CR19","first-page":"23","volume":"58","author":"J Hage","year":"2003","unstructured":"Hage, J., Harju, T., Welzl, E.: Euler graphs, triangle-free graphs and bipartite graphs in switching classes. Fundam. Informat. 58(1), 23\u201337 (2003)","journal-title":"Fundam. Informat."},{"issue":"2","key":"1_CR20","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1006\/jctb.1996.0018","volume":"66","author":"RB Hayward","year":"1996","unstructured":"Hayward, R.B.: Recognizing P$${}_{\\text{3 }}$$-structure: a switching approach. J. Comb. Theo. Ser. B 66(2), 247\u2013262 (1996)","journal-title":"J. Comb. Theo. Ser. B"},{"issue":"1\u20133","key":"1_CR21","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(98)00153-X","volume":"94","author":"A Hertz","year":"1999","unstructured":"Hertz, A.: On perfect switching classes. Discret. Appl. Math. 94(1\u20133), 3\u20137 (1999)","journal-title":"Discret. Appl. Math."},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"Kratochv\u00edl, J., Ne\u0161et\u0159il, J., Z\u00fdka, O.:. On the computational complexity of Seidel\u2019s switching. In: Annals of Discrete Mathematics, vol. 51, pp. 161\u2013166. Elsevier (1992)","DOI":"10.1016\/S0167-5060(08)70622-8"},{"key":"1_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/3-540-44849-7_17","volume-title":"Algorithms and Complexity","author":"J Gramm","year":"2003","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Graph-modeled data clustering: fixed-parameter algorithms for clique generation. In: Petreschi, R., Persiano, G., Silvestri, R. (eds.) CIAC 2003. LNCS, vol. 2653, pp. 108\u2013119. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-44849-7_17"},{"key":"1_CR24","unstructured":"Drange, P.: Parameterized graph modification algorithms. PhD thesis (2015)"},{"key":"1_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/978-3-662-49529-2_27","volume-title":"LATIN 2016: Theoretical Informatics","author":"PG Drange","year":"2016","unstructured":"Drange, P.G., Dregi, M., Sandeep, R.B.: Compressing bounded degree graphs. In: Kranakis, E., Navarro, G., Ch\u00e1vez, E. (eds.) LATIN 2016. LNCS, vol. 9644, pp. 362\u2013375. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49529-2_27"},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.jcss.2021.11.001","volume":"125","author":"D Marx","year":"2022","unstructured":"Marx, D., Sandeep, R.B.: Incompressibility of H-free edge modification problems: towards a dichotomy. J. Comput. Syst. Sci. 125, 25\u201358 (2022)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"1_CR27","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/j.disopt.2013.02.001","volume":"10","author":"S Kratsch","year":"2013","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Two edge modification problems without polynomial kernels. Discret. Optim. 10(3), 193\u2013199 (2013)","journal-title":"Discret. Optim."},{"issue":"3","key":"1_CR28","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/s00453-014-9937-x","volume":"71","author":"L Cai","year":"2015","unstructured":"Cai, L., Cai, Y.: Incompressibility of H-free edge modification problems. Algorithmica 71(3), 731\u2013757 (2015)","journal-title":"Algorithmica"},{"key":"1_CR29","unstructured":"Cai, Y.: Polynomial kernelisation of H-free edge modification problems. Mphil thesis, Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong SAR, China (2012)"},{"issue":"1","key":"1_CR30","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/s00453-011-9595-1","volume":"64","author":"Y Cao","year":"2012","unstructured":"Cao, Y., Chen, J.: Cluster editing: kernelization based on edge cuts. Algorithmica 64(1), 152\u2013169 (2012)","journal-title":"Algorithmica"},{"issue":"1","key":"1_CR31","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/s00453-021-00891-y","volume":"84","author":"Y Cao","year":"2022","unstructured":"Cao, Y., Rai, A., Sandeep, R.B., Ye, J.: A polynomial kernel for diamond-free editing. Algorithmica 84(1), 197\u2013215 (2022)","journal-title":"Algorithmica"},{"issue":"4","key":"1_CR32","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1007\/s00453-012-9619-5","volume":"65","author":"S Guillemot","year":"2013","unstructured":"Guillemot, S., Havet, F., Paul, C., Perez, A.: On the (non-)existence of polynomial kernels for $$P_\\ell $$-free edge modification problems. Algorithmica 65(4), 900\u2013926 (2013)","journal-title":"Algorithmica"},{"key":"1_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2021.08.015","volume":"891","author":"H Yuan","year":"2021","unstructured":"Yuan, H., Ke, Y., Cao, Y.: Polynomial kernels for paw-free edge modification problems. Theor. Comput. Sci. 891, 1\u201312 (2021)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR34","unstructured":"Eiben, E., Lochet, W., Saurabh, S.: A polynomial kernel for paw-free editing. In: 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, vol. 180 of LIPIcs, pp. 10:1\u201310:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"issue":"2","key":"1_CR35","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/3196834","volume":"10","author":"I Bliznets","year":"2018","unstructured":"Bliznets, I., Cygan, M., Komosa, P., Pilipczuk, M.: Hardness of approximation for H-free edge modification problems. ACM Trans. Comput. Theory 10(2), 91\u2013932 (2018)","journal-title":"ACM Trans. Comput. Theory"},{"issue":"12","key":"1_CR36","doi-asserted-by":"publisher","first-page":"2747","DOI":"10.1016\/j.dam.2008.08.022","volume":"157","author":"M Kami\u0144ski","year":"2009","unstructured":"Kami\u0144ski, M., Lozin, V.V., Milani\u010d, M.: Recent developments on graphs of bounded clique-width. Discret. Appl. Math. 157(12), 2747\u20132761 (2009)","journal-title":"Discret. Appl. Math."},{"issue":"7","key":"1_CR37","doi-asserted-by":"publisher","first-page":"1859","DOI":"10.1007\/s00453-020-00677-8","volume":"82","author":"FV Fomin","year":"2020","unstructured":"Fomin, F.V., Golovach, P.A., Str\u00f8mme, T.J.F., Thilikos, D.M.: Subgraph complementation. Algorithmica 82(7), 1859\u20131880 (2020)","journal-title":"Algorithmica"},{"key":"1_CR38","doi-asserted-by":"crossref","unstructured":"Buchanan, C., Purcell, C., Rombach, P.: Subgraph complementation and minimum rank. Electron. J. Comb., 29(1) (2022)","DOI":"10.37236\/10383"},{"key":"1_CR39","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"}],"container-title":["Lecture Notes in Computer Science","LATIN 2022: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-20624-5_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T23:04:17Z","timestamp":1667084657000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-20624-5_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031206238","9783031206245"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-20624-5_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"29 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Guanajuato","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Mexico","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 November 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/delta.cs.cinvestav.mx\/~francisco\/Latin22\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"114","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"46","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"40% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"8.7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}