# Polynomial Kernel for Interval Vertex Deletion

Polynomial Kernel for Interval Vertex Deletion Given a graph G and an integer k, the Interval Vertex Deletion (IVD) problem asks whether there exists a subset S⊆ V(G) of size at most k such that G-S is an interval graph. This problem is known to be NP-complete (according to Yannakakis at STOC 1978). Originally in 2012, Cao and Marx showed that IVD is fixed parameter tractable: they exhibited an algorithm with running time 10k nO(1). The existence of a polynomial kernel for IVD remained a well-known open problem in parameterized complexity. In this article, we settle this problem in the affirmative. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

# Polynomial Kernel for Interval Vertex Deletion

, Volume 19 (2): 68 – Apr 15, 2023
68 pages
{"ft_lang_label":"__label__en","ft_lang_prob":0.7867951,"math_prob":0.7162227,"size":4944,"snap":"2023-40-2023-50","text_gpt3_token_len":1137,"char_repetition_ratio":0.15809716,"word_repetition_ratio":0.32751092,"special_character_ratio":0.19983819,"punctuation_ratio":0.13681592,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9519145,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12],"im_url_duplicate_count":[null,1,null,1,null,1,null,1,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-06T09:26:33Z\",\"WARC-Record-ID\":\"<urn:uuid:ae08da95-2e4a-4c92-a358-f24fd00080b2>\",\"Content-Length\":\"386119\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:234ebc1c-c97a-4688-8d8e-f7de278cd9c0>\",\"WARC-Concurrent-To\":\"<urn:uuid:a8fa527f-0c03-41e8-baa2-4fb4607707d7>\",\"WARC-IP-Address\":\"35.186.214.25\",\"WARC-Target-URI\":\"https://gas-dd.sagepub.com/lp/association-for-computing-machinery/polynomial-kernel-for-interval-vertex-deletion-0f9yllQuNW\",\"WARC-Payload-Digest\":\"sha1:KMKFER6CXQAVCBVYWYQTBSHFRI33CCOQ\",\"WARC-Block-Digest\":\"sha1:2VGHERNWYRX2J57FHAAIWD2O4WRQJR6R\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100583.31_warc_CC-MAIN-20231206063543-20231206093543-00318.warc.gz\"}"}