User paul wollan - MathOverflow

Answer by Paul Wollan for Finding all paths on undirected graph

2012-04-26T21:33:57Z

There is an easy way to partition the set of $s$-$t$ paths in a graph $G$. Fix an edge $tt'$ in $G$. Let $P_1$ be the set of paths from $s$ to $t$ which use the edge $tt'$, and let $P_2$ be the set of paths from $s$ to $t$ in $G-tt'$. Then $P_1 \cap P_2 = \emptyset$ and the set of $s$-$t$ paths $P = P_1 \cup P_2$. Moreover, there is a one to one correspondence between the set of paths $P_1$ and the set of $s$-$t'$ paths in the graph $G-t$.

Thus, we get an easy recursive algorithm to find the set of paths $s$-$t$ paths in a graph $G$. Pick an edge $tt'$ incident the vertex $t$ and recursively calculate the sets $P_1$ and $P_2$. With a small amount of pre-processing, we can ensure that the runtime is $O(m(p+1))$ where $m$ is the number of edges and $p$ is the number of $s$-$t$ paths.

To make the recurrence relation on the runtime work, consider the following. We can test in time $O(m)$ if a given graph $G$ and pair of vertices $s$ and $t$ if $G$ has 0, exactly one, or at least two distinct $s$-$t$ paths. To see this, simply find the block decomposition of the graph and, and check if there is any non-trivial block between $s$ and $t$ in the tree.

We can push this slightly farther. Given an instance of the problem $G$ and vertices $s$ and $t$, we can reduce the problem in time $O(m)$ to a graph $\bar{G}$ and vertices $x$ and $y$ such that for all edges $xx'$ incident to $x$, we have that

$xx'$ is in some $y$-$x$ path,
there exists a $y$-$x'$ path in $\bar{G}-x$.

To see this, again using the block decomposition, we contract any bridge in the graph and delete edges not contained in any $s$-$t$ path. As above, this can be done in $O(m)$ time.

We give an $O(m(p-1))$ time algorithm to find the set of $s$-$t$ paths in a given graph $G$ with at least two $s$-$t$ paths.

We may assume, as above, that every edge $tt'$ incident to $t$ is contained in some $s$-$t$ path and that there exists at least one $s$-$t'$ path in $G-t$.
Check if the number of $s$-$t$ paths in $G-tt'$ is at least two, and if not, let $P_1$ be the set of the unique $s$-$t$ path in $G-tt'$. If there are at least two such paths, we recursively find the set of all such paths. Let $p_1 = |P_1|$. By choice of $tt'$, $p_1 \ge 1$.
Check if the number of $s$-$t'$ paths in $G-t$ is at least two, and if not let $P_2$ be the set of the unique $s$-$t'$ path in $G-t$. Otherwise, we recursively find the set $P_2$ of $s$-$t'$ path in $G-t$. Let $p_2 = |P_2|$, and as above, we again have $p_2 \ge 1$.

Step 1 can be performed in $c'm$ operations for some constant $c'$. The initial check in steps $2$ and $3$ can be performed in $c'(m-1)$ steps. If we must recursively run the algorithm, this will require another $c(m-1)(p_i - 1)$ operations for $i = 1, 2$ in Steps 2 and 3, respectively. As $p_i \ge 1$, we can bound the work in each of Steps 2 and 3 by $c'm + cm(p_i - 1)$. Thus, the total number of operations is at most $3c'm + c(m)(p_1 +p_2 - 2) \le cm(p-1)$ if we choose $c \ge 3c'$.

Answer by Paul Wollan for Small 4-chromatic coin graphs

2012-04-02T21:54:50Z

Flo's example with 11 is best possible. Let $G$ be a minimal coin-graph which chromatic number four. Then $G$ does not have a cut vertex, nor a vertex of degree at most two. Moreover, there does not exist a separation $(A, B)$ of $G$ of order two with $G[A \cap B]$ an edge (as opposed to a pair of non-adjacent vertices). Otherwise we could 3-color $G[A]$ and $G[B]$ and glue the colorings together to get a coloring of $G$.

Since $G$ is 2-connected, every face is bounded by a cycle. Consider the cycle $C$ bounding the infinite face. The cycle $C$ must be induced, as otherwise there is a 2-separation whose cut set is an edge. $G$ has no vertex of degree two, so every vertex of $C$ has a neighbor in $V(G) - V(C)$ (and specifically, there is at least one such vertex).

If there is exactly one vertex in $V(G) - V(C)$, then it is adjacent every vertex of $C$ and $G$ is a wheel on 7 vertices which is 3-colorable. Thus, there exist at least two vertices in $V(G) - V(C)$. However, then $|V(C)| \ge 8$. If $|V(G)| \le 10$, then $|V(C)| = 8$, and there are exactly two vertices in $V(G) - V(C)$. It follows that the graph $G$ must be equal to an 8-cycle $C$ with vertices $v_1, \dots, v_8$ and two additional vertices $x, y$, each adjacent to a subset of the vertices ${v_1, \dots, v_8}$.

For each of the vertices $x$ and $y$, their neighbors must form a subpath of $C$, say $P_x$ and $P_y$. The paths $P_x$ and $P_y$ can intersect only at their endpoints. Given that $G$ is a coin graph, $|V(P_x)| \le 5$ and $|V(P_y)| \le 5$, and we see now that there are two possible cases: either $|V(P_x)| = |V(P_y)| = 5$ and $P_x$ and $P_y$ have both endpoints in common, or alternatively, $|V(P_x)| = |V(P_y)| = 4$ and $P_x$ and $P_y$ are disjoint. In either case, the resulting graph is 3-colorable, a contradiction.

Answer by Paul Wollan for positive weighted directed graphs

2012-03-05T21:29:19Z

I assume that when you say the weight of any circuit is positive, you mean that for every directed cycle $C$, $\sum_{e \in E(C)} w(e) > 0$. There's a similar model of group labeled graphs where you calculate the weight of a circuit by either adding or subtracting $w(e)$ depending on whether you traverse the edge according to the direction or not.

The answer to 2. is "yes" if we assume the graph has every edge contained in a cycle. First, observe that it suffices to prove it for rational weights - just subtract a tiny epsilon from each edge to make it's weight rational without altering the fact that each cycle has positive weight.

Your operation for finding an equivalent weight function on the edges can be generalized: if we take any edge cut $\delta(U)$ for a subset $U \subseteq V(G)$ and a value $m \in \mathbb{R}$, then if we add $m$ to all the edges of $\delta^{in}(U)$ and subtract $m$ from $\delta^{out}(U)$, we won't change the weight of any cycle. Call this operation $resigning~on~a~cut$. (In fact, resigning on a cut $\delta(U)$ for a subset of vertices $U$ is the same as repeatedly resigning by the same value on each of vertices in $U$). Say two weight functions are $flip~equivalent$ if one can be obtained from the other by repeatedly re-signing on a cut.

A weight function is $non-negative$ if the weight of any cycle is not negative. We claim that if $G$ has the property that every edge is contained in a cycle, then any non-negative rational weight function is flip equivalent to one where every edge has non-negative weight. Assume the claim is false. It suffices to prove the claim for integer weight functions by re-scaling. Pick a counterexample on a minimal number of vertices, and subject to that, to minimize $\sum_{e \in E(G): w(e) \ge 0} w(e)$. If there exists a cycle $C$ such that $w(C) = 0$, then there exists a weight function $\bar{w}$ which is flip-equivalent to $w$ such that $\bar{w}(e) = 0$ for all edges $e \in E(C )$. To see this, number the edges of $C$ $e_1, \dots, e_k$ so that they occur in that order on $C$. We can force $e_i$ for $1 \le i \le k-1$ to have weight 0 by sequentially resigning on $\delta(v_{i+1})$. After doing so, the weight on $e_k$ will be the weight of the cycle, namely 0.

Consider the graph $G'$ obtained by contracting the cycle $C$ to a single vertex and deleting any loops which arise. Note that this preserves the property that every edge is contained in a cycle, and it also holds that each loop must have positive weight in $\bar{w}$. Let $w'$ be the weight function obtained by restricting $\bar{w}$ to the edges of $G'$. Then $G'$ has no negative weight circuit, since any such circuit could be rerouted through $C$ to give a negative weight cycle in $G$. Thus, $w'$ on $G'$ can be made non-negative by repeatedly resigning on cuts. Since each cut of $G'$ is a cut of $G$ as well, it follows that $\bar{w}$ can be made non-negative by repeatedly resigning on cuts.

Thus, we may assume that every cycle has strictly positive weight, and consequently, weight at least 1. It follows that there must exist an edge $f$ with $w(f) \ge 1$. Fix such an edge $f$, and let $w''$ be the weight function with $w''(e) = w(e)$ for all $e \neq f$ and let $w''(f) = w(f) - 1$. By construction, $w''$ is a non-negative since the weight of any cycle decreases by at most $1$. Moreover, $\sum_{e \in E(G): w''(e) \ge 0} w''(e)$ has strictly decreased, so by our choice of counterexample, there exists a weight function which is flip equivalent to $w''$ where every edge has non-negative weight. By resigning on the same series of cuts, we find a weight function which is flip equivalent to $w$ where every edge has non-negative weight, contradicting our choice of counterexample.

Now to see that the same result holds for rational weight functions where every cycle has strictly positive weight, let $z$ be such a weight function. By above there exists a weight function $z'$ which is flip-equivalent to $z$ such that every edge has $z'(e) \ge 0$. Pick such a $z'$ to have has few edges of weight zero as possible. The function $z'$ does not have any cycles where every edge has weight 0 in $z'$. Thus, if there are any edges $z'(e) = 0$, it follows that there is a vertex $v$ such that $v$ has some out edge of weight zero and no in edge of weight zero. If we let $\epsilon= min_{e \in \delta(v)} z'(e)$, then adding $\epsilon/2$ to each of the out edges of $v$ and subtracting $\epsilon/2$ from all the in edges will maintain the property of being a non-negative weighting and strictly decrease the number of edges of weight zero, a contradiction.

Answer by Paul Wollan for Counting the number of subgraphs in a given labeled tree

2012-01-27T17:49:35Z

The following algorithm should efficiently calculate the answer for the number of subtrees of a labeled graph.

Let $(T, r)$ be a labeled, rooted tree with root $r$. We first calculate the number of subtrees containing $r$. Call this value $N_1(T, r)$. If $r_1, \dots, r_k$ are the neighbors of $r$ and $T_1,\dots, T_k$ are the trees of $T-r$ such that $r_i \in V(T_i)$ for $1 \le i \le k$, then

$N_1(T, r) = \prod_1^k \left( N_1(T_i, r_i) + 1 \right).$

This follows because for each neighbor $r_i$ of $r$, we have a choice of $N_1(T_i, r_i)$ possible trees or alternatively, the empty tree.

This formula gives a recursive algorithm to calculate $N_t(T, r)$. Since the total number of vertices in the trees decreases in each iteration of the algorithm, we get an easy $O(n^2)$ bound on the run-time.

For a labeled tree $T$, let $N(T)$ be the number of distinct subtrees. Fix a leaf $v$ of $T$. Then $N(T) = N(T-v) + N_1(T, v)$. Thus, again we get a recursive algorithm with a bound of $O(n^3)$ on the run-time. It might be possible to get better bounds on the run-time of the algorithms.

The specific value of $N(T)$ will depend a lot on the tree $T$. For example, if $T$ is the path on $n$ vertices, then $N(T) = O(n^2)$. Alternatively, if $T$ is the star on $n$ vertices, then $N(T) = O(2^n)$.

Comment by Paul Wollan

2012-04-10T21:33:40Z

Does there exist an example where an optimal partition must have partitions inducing non-connected graphs? The second point in the proposer's statement seems to say "yes", but I have been unable to come up with any examples. Could it be equivalent to the problem of finding a partition of the edge set into triangles, claws and P_4's maximizing the number of triangles?

Comment by Paul Wollan

2012-04-04T14:31:03Z

Thanks Flo, that's right. So, the final claim in the proof that we must be equal to two adjacent vertices x and y each adjacent to five of the boundary vertices was not correct. I fixed the proof above.

Comment by Paul Wollan

2012-04-03T15:28:59Z

Yes, that part was a little bit hand-wavey. Fix a layout of a coin graph containing a cycle C and two additional vertices contained in the disc bounded by C. Let C' be the piecewise linear curve in the plane defined by the center of the coins of V(C). We may assume that the disc bounded by C' is convex, and so we may assume the two coins not in C are touching. If we place 8 coins around the interior pair of coins as tightly as possible, we see there exists a curve C'' of length 8 contained in the disc bounded by C'. Thus, C' has length at least 8, and if exactly 8 then C' = C''

Comment by Paul Wollan

2012-03-09T23:36:40Z

Great - glad it works. If you need the result for general graphs (i.e. not strongly connected), the proof can be extended. If there is a directed cut, inductively re-sign both halves of the cut. Performing the same operations on the original graph will leave every edge positive, except for possibly edges of the cut we decomposed on. But since it is a directed cut, we can add some arbitrarily large number to every edge of the cut and the resulting graph has every edge with positive weight.