Approximating the maximum clique minor and some subgraph homeomorphism problems.
(2007) In Theoretical Computer Science 374(13). p.149158 Abstract
 We consider the “minor” and “homeomorphic” analogues of the maximum clique problem, i.e., the problems of determining the largest h such that the input graph (on n vertices) has a minor isomorphic to Kh or a subgraph homeomorphic to Kh, respectively, as well as the problem of finding the corresponding subgraphs. We term them as the maximum clique minor problem and the maximum homeomorphic clique problem, respectively. We observe that a known result of Kostochka and Thomason supplies an O(sqrt n) source bound on the approximation factor for the maximum clique minor problem achievable in polynomial time. We also provide an independent proof of nearly the same approximation factor with explicit polynomialtime estimation, by exploiting the... (More)
 We consider the “minor” and “homeomorphic” analogues of the maximum clique problem, i.e., the problems of determining the largest h such that the input graph (on n vertices) has a minor isomorphic to Kh or a subgraph homeomorphic to Kh, respectively, as well as the problem of finding the corresponding subgraphs. We term them as the maximum clique minor problem and the maximum homeomorphic clique problem, respectively. We observe that a known result of Kostochka and Thomason supplies an O(sqrt n) source bound on the approximation factor for the maximum clique minor problem achievable in polynomial time. We also provide an independent proof of nearly the same approximation factor with explicit polynomialtime estimation, by exploiting the minor separator theorem of Plotkin et al.
Next, we show that another known result of Bollobás and Thomason and of Komlós and Szemerédi provides an O(sqrt n) source bound on the approximation factor for the maximum homeomorphic clique achievable in polynomial time. On the other hand, we show an Ω(n1/2−O(1/(logn)γ)) lower bound (for some constant γ, unless NP subset ZPTIME(2^(logn)^O(1)) on the best approximation factor achievable efficiently for the maximum homeomorphic clique problem, nearly matching our upper bound.
Finally, we derive an interesting tradeoff between approximability and subexponential time for the problem of subgraph homeomorphism where the guest graph has maximum degree not exceeding three and low treewidth. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/588104
 author
 Alon, Noga ; Lingas, Andrzej ^{LU} and Wahlén, Martin ^{LU}
 organization
 publishing date
 2007
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 Graph homeomorphism, Approximation, Graph minors
 in
 Theoretical Computer Science
 volume
 374
 issue
 13
 pages
 149  158
 publisher
 Elsevier
 external identifiers

 wos:000246170000012
 scopus:33947373382
 ISSN
 03043975
 DOI
 10.1016/j.tcs.2006.12.021
 project
 VR 20054085
 language
 English
 LU publication?
 yes
 id
 c480fd1b92cc4b3db27fd55ea1d2760a (old id 588104)
 date added to LUP
 20160401 15:22:52
 date last changed
 20200112 18:26:50
@article{c480fd1b92cc4b3db27fd55ea1d2760a, abstract = {We consider the “minor” and “homeomorphic” analogues of the maximum clique problem, i.e., the problems of determining the largest h such that the input graph (on n vertices) has a minor isomorphic to Kh or a subgraph homeomorphic to Kh, respectively, as well as the problem of finding the corresponding subgraphs. We term them as the maximum clique minor problem and the maximum homeomorphic clique problem, respectively. We observe that a known result of Kostochka and Thomason supplies an O(sqrt n) source bound on the approximation factor for the maximum clique minor problem achievable in polynomial time. We also provide an independent proof of nearly the same approximation factor with explicit polynomialtime estimation, by exploiting the minor separator theorem of Plotkin et al.<br/><br> <br/><br> Next, we show that another known result of Bollobás and Thomason and of Komlós and Szemerédi provides an O(sqrt n) source bound on the approximation factor for the maximum homeomorphic clique achievable in polynomial time. On the other hand, we show an Ω(n1/2−O(1/(logn)γ)) lower bound (for some constant γ, unless NP subset ZPTIME(2^(logn)^O(1)) on the best approximation factor achievable efficiently for the maximum homeomorphic clique problem, nearly matching our upper bound.<br/><br> <br/><br> Finally, we derive an interesting tradeoff between approximability and subexponential time for the problem of subgraph homeomorphism where the guest graph has maximum degree not exceeding three and low treewidth.}, author = {Alon, Noga and Lingas, Andrzej and Wahlén, Martin}, issn = {03043975}, language = {eng}, number = {13}, pages = {149158}, publisher = {Elsevier}, series = {Theoretical Computer Science}, title = {Approximating the maximum clique minor and some subgraph homeomorphism problems.}, url = {http://dx.doi.org/10.1016/j.tcs.2006.12.021}, doi = {10.1016/j.tcs.2006.12.021}, volume = {374}, year = {2007}, }