Efficient computation of a vertex-partition for graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T05:15:44Z http://mathoverflow.net/feeds/question/38547 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/38547/efficient-computation-of-a-vertex-partition-for-graphs Efficient computation of a vertex-partition for graphs Roland Bacher 2010-09-13T08:07:05Z 2011-03-01T05:12:13Z <p>A finite simple connected graph $\Gamma$ with vertices $V(\Gamma)$ has a partition of its vertices into (at most) two subsets defined as follows: Given a spanning tree $T\subset \Gamma$, chose a function $\varphi_T:V(\Gamma)\longrightarrow \lbrace \pm 1\rbrace$ such that $\varphi(s)\varphi(t)=-1$ if $s,t\in V(\Gamma)$ are adjacent vertices of $T$. The product $\psi=\prod_T\varphi_T$ over all spanning trees of $\Gamma$ is well defined up to a global sign and induces a partition $\psi^{-1}(1)\cup\psi^{-1}(-1)$ of $V(\Gamma)$.</p> <p>Is there an efficient way for computing this partition for an arbitrary graph?</p> <p>Remark: The best way I can think of for a general graph is to consider all partitions $A\cup B$ of $V(\Gamma)$ which induce a connected bipartite subgraph (obtained by removing all edges having either both endpoints in $A$ or in $B$) of odd complexity.</p> http://mathoverflow.net/questions/38547/efficient-computation-of-a-vertex-partition-for-graphs/38561#38561 Answer by sleepless in beantown for Efficient computation of a vertex-partition for graphs sleepless in beantown 2010-09-13T11:19:40Z 2010-09-13T11:24:51Z <p>This is effectively creating the bipartite coloring of a graph $G=(V,E)$, if it is bipartite. There can be no bipartite coloring if there are odd length cycles in the graph which you are considering.</p> <p>You can check to see if a graph is bipartite in $O(|V|\cdot |E|)$, i.e. time proportional to the product of the number of edges and vertices.</p> <p>If your graph is a single component connected finite graph, start by pick any vertex as a starting point and assign it the distance $0$ (or equivalently the label $(-1)$. Then iterate the following two steps alternately until every vertex is labeled, or until you end up attempting to assign two different labels to the same vertex (i.e. you find two different paths to the same vertex which are not the same length <em>modulo</em> $2$.</p> <ul> <li><p>follow every edge from your vertices labeled $0$ to get the next set of vertices and see if any of them are already labeled $0$, if there are then no such bipartition exists. If not, label them with the distance $1$ or alternately $(+1)$</p></li> <li><p>follow every edge from the vertices labeled $1$ to get the next set of vertices and see if any of them are already labeled $1$, if there are then no such bipartition exists. If not, label them $0$ and continue to iterate.</p></li> </ul> <p>If you end up attempting to label the same vertex with both labels/colors, then the graph is not bipartite. Otherwise, you end up with every vertex labeled with the parity ($0$=even, $1$=odd) of their distance from the initial vertex chosen for this labeling.</p> http://mathoverflow.net/questions/38547/efficient-computation-of-a-vertex-partition-for-graphs/56963#56963 Answer by Aaron Meyerowitz for Efficient computation of a vertex-partition for graphs Aaron Meyerowitz 2011-03-01T04:54:28Z 2011-03-01T05:12:13Z <p>As you note, for a bipartite graph you get either the bipartition or the trivial partition (according as the number of spanning trees is even or odd). Any edge whose removal (keeping its endpoints) disconnects the graph must be in every spanning tree. So its two ends will be in the same or opposite parts of the partition according as the total number of spanning trees is even or odd. So we may delete all these edges since the number of spanning trees for the given graph will be the same as the number of maximal spanning forests of the reduced graph. The reduced graph has one or more connected components each without degree one vertices or bridges. Each of these components is either two connected or has one or more cutpoints separating it into maximal 2 connected components. If any of those 2 connected components has an even number of spanning trees then the reduced graph gets the trivial partition. </p> <p>I think it might be more interesting to have each spanning tree vote if each pair of vertices are "the same" or "opposite" (so "neutral" is a possible outcome)</p>