Advanced

Approximating the maximum clique minor and some subgraph homeomorphism problems.

Alon, Noga; Lingas, Andrzej LU and Wahlén, Martin LU (2007) In Theoretical Computer Science 374(1-3). p.149-158
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 polynomial-time 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 polynomial-time 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 trade-off 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:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Graph homeomorphism, Approximation, Graph minors
in
Theoretical Computer Science
volume
374
issue
1-3
pages
149 - 158
publisher
Elsevier
external identifiers
  • wos:000246170000012
  • scopus:33947373382
ISSN
0304-3975
DOI
10.1016/j.tcs.2006.12.021
project
VR 2005-4085
language
English
LU publication?
yes
id
c480fd1b-92cc-4b3d-b27f-d55ea1d2760a (old id 588104)
date added to LUP
2007-10-31 10:59:49
date last changed
2017-01-01 06:38:33
@article{c480fd1b-92cc-4b3d-b27f-d55ea1d2760a,
  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 polynomial-time 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 trade-off 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         = {0304-3975},
  keyword      = {Graph homeomorphism,Approximation,Graph minors},
  language     = {eng},
  number       = {1-3},
  pages        = {149--158},
  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},
  volume       = {374},
  year         = {2007},
}