hide
Free keywords:
-
Abstract:
We study the expected time complexity of two graph partitioning
problems: the graph coloring and the cut into equal parts.
If $k=o(\sqrt{n/\log n})$, we can test whether two vertices of a $k$-colorable
graph can be $k$-colored by the same color in time $O(k\log n)$ per pair of
vertices with
$O(k^4\log^3n)$-time preprocessing in such a way that for almost all $k$-colorable
graphs the answer is correct for all pairs of vertices.
As a consequence, we obtain a sublinear (with respect to the number of edges)
expected time algorithm for $k$-coloring
of $k$-colorable graphs (assuming the uniform input distribution).
Similarly, if $ c\le (1/8-\epsilon)n^2 $, $ \epsilon>0 $ a constant,
and $G$ is a graph having cut of the vertex
set into two equal parts with at most $c$ cross-edges, we can test whether two
vertices belong to the same class of some $c$-cut in time $O(\log n)$ per vertex
with $O(\log^3n)$-time preprocessing in such a way that for almost all graphs
having a $c$-cut the answer is correct for all pairs of vertices.
The methods presented in the paper can also be used to other graph partitioning
problems, e.g. the largest clique or independent subset.
