Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels

B.M.P. Jansen, D. Marx

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

20 Citations (Scopus)

Abstract

We study two fundamental problems related to finding subgraphs: (1) given graphs G and H, Subgraph Test asks if H is isomorphic to a subgraph of G, (2) given graphs G, H, and an integer t, PACKING asks if G contains t vertex-disjoint subgraphs isomorphic to H. For every graph class F, let F-Subgraph Test and F-Packing be the special cases of the two problems where H is restricted to be in F. Our goal is to study which classes F make the two problems tractable in one of the following senses: - (randomized) polynomial-time solvable, - admits a polynomial (many-one) kernel (that is, has a polynomial-time preprocessing procedure that creates an equivalent instance whose size is polynomially bounded by the size of the solution), or - admits a polynomial Turing kernel (that is, has an adaptive polynomial-time procedure that reduces the problem to a polynomial number of instances, each of which has size bounded polynomially by the size of the solution). To obtain a more robust setting, we restrict our attention to hereditary classes F. It is known that if every component of every graph in F has at most two vertices, then F-Packing is polynomial-time solvable, and NP-hard otherwise. We identify a simple combinatorial property (every component of every graph in F either has bounded size or is a bipartite graph with one of the sides having bounded size) such that if a hereditary class F has this property, then F-Packing admits a polynomial kernel, and has no polynomial (many-one) kernel otherwise, unless the polynomial hierarchy collapses. Furthermore, if F does not have this property, then F-Packing is either WK-hard, W-hard, or Long Path-hard, giving evidence that it does not admit polynomial Turing kernels either. For F-Subgraph Test, we show that if every graph of a hereditary class F satisfies the property that it is possible to delete a bounded number of vertices such that every remaining component has size at most two, then F-Subgraph Test is solvable in randomized polynomial time and it is NP-hard otherwise. We introduce a combinatorial property called (a, b, c, d)-splittability and show that if every graph in a hereditary class F has this property, then F-Subgraph Test admits a polynomial Turing kernel and it is WK-hard, W-hard, or Long Path-hard otherwise. We do not give a complete characterization of the cases when F-Subgraph Test admits polynomial many-one kernels, but show examples that this question is much more fragile than the characterization for Turing kernels.
Original language English Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15, San Diego CA, USA, January 4-6, 2015) Philadelphia Society for Industrial and Applied Mathematics (SIAM) 616-629 978-1-61197-374-7 https://doi.org/10.1137/1.9781611973730.42 Published - 2015 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015) - Westin San Diego Gaslamp Quarter, San Diego, United StatesDuration: 4 Jan 2015 → 6 Jan 2015Conference number: 26http://www.siam.org/meetings/da15/

Conference

Conference 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015) SODA '15 United States San Diego 4/01/15 → 6/01/15 Event co-located with the 17th Workshop on Algorithm Engineering and Experiments (ALENEX '15) and the 12th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '15) http://www.siam.org/meetings/da15/

Fingerprint

Dive into the research topics of 'Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels'. Together they form a unique fingerprint.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8697822,"math_prob":0.68944514,"size":3516,"snap":"2022-05-2022-21","text_gpt3_token_len":841,"char_repetition_ratio":0.119874716,"word_repetition_ratio":0.051948052,"special_character_ratio":0.22952218,"punctuation_ratio":0.084375,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9654247,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-01-20T19:23:56Z\",\"WARC-Record-ID\":\"<urn:uuid:bdbd6e97-23c5-4d78-8cf8-31ebc6b96bce>\",\"Content-Length\":\"59279\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:b1752f1b-e1a7-4c5d-b9b1-d8a9503f5ca5>\",\"WARC-Concurrent-To\":\"<urn:uuid:9e31bd0c-417f-4aa6-8f51-5d5ad771899e>\",\"WARC-IP-Address\":\"34.248.98.230\",\"WARC-Target-URI\":\"https://research.tue.nl/en/publications/characterizing-the-easy-to-find-subgraphs-from-the-viewpoint-of-p\",\"WARC-Payload-Digest\":\"sha1:HTHFGD5WNG7MJGGZXB3T3KNAHUMWHTX6\",\"WARC-Block-Digest\":\"sha1:7J4RG5Q7CI65243DZVSKXXYDNYG5H4XV\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-05/CC-MAIN-2022-05_segments_1642320302622.39_warc_CC-MAIN-20220120190514-20220120220514-00577.warc.gz\"}"}