Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-039 | 21st April 2004 00:00

On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems


Authors: Andrzej Lingas, Martin Wahlén
Publication: 2nd May 2004 17:05
Downloads: 2941


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 has a minor isomorphic to $K_h$ or a subgraph homeomorphic to $K_h,$ respectively.We show the former to be approximable within $O(\sqrt {n} \log^{1.5} n)$ by exploiting the minor separator theorem of Plotkin {\em et al.}
Next, we showan $\Omega (n^{1/2 - O(1/(\log n)^{\gamma})})$ lower bound (for some constant $\gamma $, unless $\mathcal{NP} \subseteq \text{ZPTIME}(2^{(\log n )^{O(1)}})),$ and an $O(n\log \log n /\log^{1.5}n)$ upper bound on the approximation factor for maximum homeomorphic clique.Finally, we study the problem of subgraph homeomorphism where the guest graph has maximum degree not exceeding three and low treewidth. In particular, we show that for any graph $G$ on $n$ vertices and a positive integer $q$ not exceeding $n,$ one can produce either $n/q$ approximation to the longest cycle problem and $(n-1)/(q-1)$ approximation to the longest path problem, both in polynomial time, or a longest cycle and a longest path of $G$ in time $2^{O(q\sqrt {n}\log^{2.5} n)}.$

ISSN 1433-8092 | Imprint