Search

We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs.

The complexity of the subgraph isomorphism problem where the pattern graph is of fixed size is well known to depend on the topology of the pattern graph. For instance, the larger the maximum independent set of the pattern graph is the more efficient algorithms are known. The situation seems to be substantially different in the case of induced subgraph isomorphism for pattern graphs of fixed size. We present two results which provide evidence that no topology of an induced subgraph of fixed size can be easier to detect or count than an independent set of related size. We show that: Any fixed pattern graph that has a maximum independent set of size k that is disjoint from other maximum independent sets is not easier to detect as an induced subgraph than an independent set of size k. It follows in particular that an induced path on k vertices is not easier to detect than an independent set on ⌈k/2 ⌉ vertices, and that an induced even cycle on k vertices is not easier to detect than an independent set on k/2 vertices. In view of linear time upper bounds on induced paths of length three and four, our lower bound is tight. Similar corollaries hold for the detection of induced complete bipartite graphs and induced complete split graphs. For an arbitrary pattern graph H on k vertices with no isolated vertices, there is a simple subdivision of H, resulting from splitting each edge into a path of length four and attaching a distinct path of length three at each vertex of degree one, that is not easier to detect or count than an independent set on k vertices, respectively. Finally, we show that the so called diamond, paw and C 4 are not easier to detect as induced subgraphs than an independent set on three vertices.

Given a pattern graph H of fixed size, and a host graph G guaranteed to contain at most one occurrence of a subgraph isomorphic to H, we show that both the problem of finding such an occurrence (if any) as well as the decision version of the problem are as hard as in the general case when G may contain several occurrences of H.

We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. For an undirected graph G of unknown girth k, our algorithm returns with high probability a cycle of length at most 2k for even k and 2k + 2 for odd k, in time O(n3/2 √log n). Thus, in general, it yields a 2 2/3 approximation. We study also the problem of finding a simple cycle of minimum total weight in an undirected graph with nonnegative edge weights. We present a simple combinatorial 2-approximation algorithm for a minimum weight (simple) cycle in an undirected graph with nonnegative integer edge weights in the range {1, 2, ..., M}. This algorithm runs in time O(n2 log n log M).

We present a general framework for computing various optimal embeddings of undirected and directed connected graphs in two and multi-dimensional integer lattices in time sub-exponential either in the minimum number n of lattice points used by such optimal embeddings or in the budget upper bound b on the number of lattice points that may be used in an embedding. The sub-exponential upper bounds in the two dimensional case and d-dimensional case are respectively of the form 2\(^{O(\sqrt{ln}log n)}\), 2\(^{O(\sqrt{lb}log b)}\) and 2\(^{O(dl^{1/d_n (d-1)/d}{\rm log} n)}\), 2\(^{O(dl^{1/d_b (d-1)/d}{\rm log} b)}\), where l stands for the degree of the allowed overlap. For the problem of minimum total edge length planar or multi-dimensional embedding or layout of a graph and the problem of an optimal protein folding in the so called HP model we obtain the upper bounds in terms of n. Note that in case of protein folding n is also the size of the input. The list of problems for which we can derive the upper bounds in terms of b includes among other things