3
$\begingroup$

An $(s,f)$- balanced separator in a graph $G$ is a set $S$ of $s$ vertices removing which yields connected compoennts of size at most $f|V|$. If the vertices of $S$ form a cycle of length $s$, $S$ is said to be a cycle-separator.

Question: for which smallest value of $\frac{s}{\sqrt{n}}$ such that $f$ is a constant there exists (and one which can be found in polynomial time) an $(s,f)$-cycle separator for all biconnected planar graphs which are not "easy" - the notion of easiness being (for example) bounded tree-width. Probably the parameters $s,f$ will depend on the tree-width $w$ of the easy class.

Notice that I do not care about $f$ as long as it is a constant but $s$ (as a fraction of $\sqrt{n}$) is crucial for me.

Some background: Lipton-Tarjan gave a $(c\sqrt{n},\frac{2}{3})$-balanced planar (vertex) separator for some constant $c$. Subsequently Miller gave a similar separator that is also a cycle but in triangulated planar graphs.

If we omit the triangulated condition (say replace it by $2$-vertex connected) there might not exist an $(O(\sqrt{n}),O(1))$-cycle separator - case in point being a cycle on $n$ vertices. We can choose to ignore such easy (e.g. all bounded tree-width) cases.

$\endgroup$
  • 1
    $\begingroup$ What's the desired behavior on the following family of graphs? For $k,l$ with $kl=n$ and $k \le l$, form a grid graph with $k$ rows and $l+1$ columns and then identify the left-most column with the right-most column. It's planar, the treewidth is around $k$, and it seems like any cyclic separator would need size $\Omega(l)$ to achieve constant $f$. So with say $k = n^\epsilon$, you get large treewidth, but still need a fairly large separator. Is there another sense in which such graphs are "easy"? $\endgroup$ – Andrew Morgan Nov 28 '16 at 21:51
  • $\begingroup$ @AndrewMorgan Point well made. This is indeed a hard instance for a single cycle separator. But maybe if I allowed 2 cycle-separators or in general O(1) many cycles which separate the graph in a balanced way - then this would be taken care of. However, that may lead us far afield and require a different technique for separator computation. In the meantime if you convert your comment to an impossibility answer I will mark it as the correct answer. Thanks! $\endgroup$ – SamiD Nov 30 '16 at 20:38
2
$\begingroup$

This doesn't seem to be possible, at least not without finding the right notion of "easy".

Consider a graph formed by taking a grid graph with $k$ rows and $l+1$ columns, and identifying the leftmost column of vertices with the rightmost column of vertices. Here, we have $n = kl$ vertices, and we're interested in $k \le l$. The graph is planar, and has treewidth at least $k$, as it has a $k\times k$ grid graph as a minor.

Additionally, a cyclic separator achieving constant $f$ in this graph seems to need $\Omega(l)$ vertices (where the constant depends on $f$). Imagine the graph drawn on a cylinder of circumference $l$ and height $k$, where the graph forms an equally spaced grid on the surface of the cylinder. Then if a cyclic separator has length less than $l$, it cannot "go around" the cylinder. Hence a cyclic separator gives a way to find a region in a $k\times l$ rectangle whose perimeter is the length of the separator, and whose area is at least a constant ($1-f$) fraction of the whole rectangle's area. I don't know the exact isoperimetric inequality for this, but it seems like such a region would need perimeter $\Omega(l)$ in order to have enough area and fit into the rectangle.

Thus we have a graph with treewidth $k$ and whose separators need to be of size $\Omega(l)$. Choosing parameters like $k = n^\epsilon$ and $l = n^{1-\epsilon}$, we thus see that a cyclic $(s,f)$-separator for constant $f$ needs to have $s = \Omega(n^{1-\epsilon})$, even for graphs with treewidth $n^\epsilon$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.