{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T04:06:32Z","timestamp":1751601992891,"version":"3.41.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,4,5]],"date-time":"2018-04-05T00:00:00Z","timestamp":1522886400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,1]]},"DOI":"10.1007\/s00453-018-0431-8","type":"journal-article","created":{"date-parts":[[2018,4,5]],"date-time":"2018-04-05T13:42:05Z","timestamp":1522935725000},"page":"26-46","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs"],"prefix":"10.1007","volume":"81","author":[{"given":"Neeldhara","family":"Misra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashutosh","family":"Rai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,4,5]]},"reference":[{"issue":"7","key":"431_CR1","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1016\/j.dam.2008.08.020","volume":"158","author":"L Addario-Berry","year":"2010","unstructured":"Addario-Berry, L., Kennedy, W.S., King, A.D., Li, Z., Reed, B.A.: Finding a maximum-weight induced k-partite subgraph of an i-triangulated graph. Discret. Appl. Math. 158(7), 765\u2013770 (2010)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"431_CR2","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/s00453-010-9428-7","volume":"61","author":"N Alon","year":"2011","unstructured":"Alon, N., Gutin, G.Z., Kim, E.J., Szeider, S., Yeo, A.: Solving MAX-r-SAT above a tight lower bound. Algorithmica 61(3), 638\u2013655 (2011)","journal-title":"Algorithmica"},{"issue":"2","key":"431_CR3","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1002\/net.3230190206","volume":"19","author":"E Balas","year":"1989","unstructured":"Balas, E., Yu, C.S.: On graphs with polynomially solvable maximum-weight clique problem. Networks 19(2), 247\u2013253 (1989)","journal-title":"Networks"},{"key":"431_CR4","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets m\u00f6bius: fast subset convolution. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 67\u201374. San Diego, 11\u201313 June (2007)","DOI":"10.1145\/1250790.1250801"},{"key":"431_CR5","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Analysis of data reduction: transformations give evidence for non-existence of polynomial kernels. In: Technical Report, (2008)"},{"key":"431_CR6","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Kernelization: new upper and lower bound techniques. In: IWPEC, pp. 17\u201337. (2009)","DOI":"10.1007\/978-3-642-11269-0_2"},{"issue":"8","key":"431_CR7","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"431_CR8","doi-asserted-by":"publisher","first-page":"44:1","DOI":"10.1145\/2973749","volume":"63","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. J. ACM 63(5), 44:1\u201344:69 (2016)","journal-title":"J. ACM"},{"key":"431_CR9","unstructured":"Byskov, J.M.: Algorithms for k-colouring and finding maximal independent sets. In: SODA, pp. 456\u2013457. (2003)"},{"issue":"6","key":"431_CR10","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/j.orl.2004.03.002","volume":"32","author":"JM Byskov","year":"2004","unstructured":"Byskov, J.M.: Enumerating maximal independent sets with applications to graph colouring. Oper. Res. Lett. 32(6), 547\u2013556 (2004)","journal-title":"Oper. Res. Lett."},{"key":"431_CR11","doi-asserted-by":"crossref","unstructured":"Dabrowski, K., Lozin, V.V., M\u00fcller, H., Rautenbach, D.: Parameterized algorithms for the independent set problem in some hereditary graph classes. In IWOCA, Volume 6460 of Lecture Notes in Computer Science, pp. 1\u20139. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-19222-7_1"},{"issue":"4","key":"431_CR12","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/2629620","volume":"61","author":"H Dell","year":"2014","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM 61(4), 23:1\u201323:27 (2014)","journal-title":"J. ACM"},{"issue":"2","key":"431_CR13","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/2650261","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and ids. ACM Trans. Algorithms 11(2), 13:1\u201313:20 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"431_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"431_CR15","unstructured":"Drange, P.G., Dregi, M.S., Fomin, F.V., Kreutzer, S., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M. Reidl, F., Villaamil, F.S., Saurabh, S., Siebertz, S., Sikdar, S.: Kernelization and sparseness: the case of dominating set. In: 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, pp. 31:1\u201331:14. Orl\u00e9ans, 17\u201320 February 2016"},{"issue":"2","key":"431_CR16","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/j.disc.2017.09.012","volume":"341","author":"HP Cray du","year":"2018","unstructured":"du Cray, H.P., Sau, I.: Improved FPT algorithms for weighted independent set in bull-free graphs. Discrete Math. 341(2), 451\u2013462 (2018)","journal-title":"Discrete Math."},{"key":"431_CR17","volume-title":"Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer, New York (2006)"},{"issue":"2","key":"431_CR18","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00453-007-9152-0","volume":"52","author":"FV Fomin","year":"2008","unstructured":"Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the minimum feedback vertex set problem: exact and enumeration algorithms. Algorithmica 52(2), 293\u2013307 (2008)","journal-title":"Algorithmica"},{"key":"431_CR19","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: SODA, pp. 503\u2013510, (2010)","DOI":"10.1137\/1.9781611973075.43"},{"issue":"4","key":"431_CR20","doi-asserted-by":"publisher","first-page":"29:1","DOI":"10.1145\/2886094","volume":"63","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29:1\u201329:60 (2016)","journal-title":"J. ACM"},{"issue":"1","key":"431_CR21","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct pcps for NP. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"431_CR22","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1007\/s00453-013-9837-5","volume":"71","author":"E Ghosh","year":"2015","unstructured":"Ghosh, E., Kolay, S., Kumar, M., Misra, P., Panolan, F., Rai, A., Ramanujan, M.S.: Faster parameterized algorithms for deletion to split graphs. Algorithmica 71(4), 989\u20131006 (2015)","journal-title":"Algorithmica"},{"issue":"1","key":"431_CR23","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31\u201345 (2007)","journal-title":"SIGACT News"},{"issue":"4","key":"431_CR24","doi-asserted-by":"publisher","first-page":"1758","DOI":"10.1137\/09077850X","volume":"26","author":"S Gupta","year":"2012","unstructured":"Gupta, S., Raman, V., Saurabh, S.: Maximum r-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds. SIAM J. Discrete Math. 26(4), 1758\u20131780 (2012)","journal-title":"SIAM J. Discrete Math."},{"key":"431_CR25","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1112\/plms\/s2-17.1.75","volume":"17","author":"GH Hardy","year":"1918","unstructured":"Hardy, G.H., Ramanujan, S.: Asymptotic formulae in combinatory analysis. Proc. Lond. Math. Soc. 17, 75\u2013115 (1918)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"1","key":"431_CR26","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s00224-017-9805-6","volume":"62","author":"EC Hols","year":"2018","unstructured":"Hols, E.C., Kratsch, S.: A randomized polynomial kernel for subset feedback vertex set. Theor. Comput. Syst. 62(1), 63\u201392 (2018)","journal-title":"Theor. Comput. Syst."},{"issue":"2","key":"431_CR27","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S Khot","year":"2002","unstructured":"Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci. 289(2), 997\u20131008 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"431_CR28","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Representative sets and irrelevant vertices: new tools for kernelization. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, pp. 450\u2013459. New Brunswick, 20\u201323 October 2012","DOI":"10.1109\/FOCS.2012.46"},{"issue":"4","key":"431_CR29","first-page":"20:1","volume":"10","author":"S Kratsch","year":"2014","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Compression via matroids: a randomized polynomial kernel for odd cycle transversal. ACM Trans. Algorithms 10(4), 20:1\u201320:15 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"431_CR30","first-page":"55","volume-title":"Selected Topics in Graph Theory","author":"L Lovasz","year":"1983","unstructured":"Lovasz, L.: Perfect graphs. In: Beineke, L.W., Wilson, R.J. (eds.) Selected Topics in Graph Theory, vol. 2, pp. 55\u201367. Academic Press, London (1983)"},{"key":"431_CR31","doi-asserted-by":"crossref","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In FOCS, pp. 182\u2013191. (1995)","DOI":"10.1109\/SFCS.1995.492475"},{"key":"431_CR32","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed Parameter Algorithms (Oxford Lecture Series in Mathematics and Its Applications)","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed Parameter Algorithms (Oxford Lecture Series in Mathematics and Its Applications). Oxford University Press, Oxford (2006)"},{"key":"431_CR33","doi-asserted-by":"crossref","unstructured":"Philip, G., Rai, A., Saurabh, S.: Generalized pseudoforest deletion: algorithms and uniform kernel. In: Mathematical Foundations of Computer Science 2015\u201440th International Symposium Part II, MFCS 2015, Milan, pp. 517\u2013528. 24\u201328 August 2015","DOI":"10.1007\/978-3-662-48054-0_43"},{"issue":"3","key":"431_CR34","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s00224-007-1334-2","volume":"41","author":"V Raman","year":"2007","unstructured":"Raman, V., Saurabh, S., Sikdar, S.: Efficient exact algorithms through enumerating maximal independent sets and other techniques. Theor. Comput. Syst. 41(3), 563\u2013587 (2007)","journal-title":"Theor. Comput. Syst."},{"issue":"2","key":"431_CR35","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s00453-007-9148-9","volume":"52","author":"V Raman","year":"2008","unstructured":"Raman, V., Saurabh, S.: Short cycles make w-hard problems hard: FPT algorithms for w-hard problems in graphs with no short cycles. Algorithmica 52(2), 203\u2013225 (2008)","journal-title":"Algorithmica"},{"issue":"3","key":"431_CR36","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/s00453-015-0083-x","volume":"77","author":"S Thomass\u00e9","year":"2017","unstructured":"Thomass\u00e9, S., Trotignon, N., Vuskovic, K.: A polynomial turing-kernel for weighted independent set in bull-free graphs. Algorithmica 77(3), 619\u2013641 (2017)","journal-title":"Algorithmica"},{"key":"431_CR37","unstructured":"Trotignon, N.: Perfect graphs: a survey. CoRR, arXiv:abs\/1301.5149 , (2013)"},{"issue":"3","key":"431_CR38","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505\u2013517 (1977)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"431_CR39","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(87)90107-4","volume":"24","author":"M Yannakakis","year":"1987","unstructured":"Yannakakis, M., Gavril, F.: The maximum k-colorable subgraph problem for chordal graphs. Inf. Process. Lett. 24(2), 133\u2013137 (1987)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0431-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0431-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0431-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T13:02:44Z","timestamp":1751547764000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0431-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,5]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["431"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0431-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,4,5]]},"assertion":[{"value":"10 May 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 April 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}