-1
$\begingroup$

I want to find a minimal vertex in a tree from which we can traverse some edges exactly twice then come back to that vertex then do it with the rest of edges. By minimal, I mean that the difference of numbers of two subsets of edges have to be minimum.

$\endgroup$
5
  • $\begingroup$ The problem is probably easy ... but it is poorly stated. In your first graph, starting from vertex 2, you can traverse only one edge at a time out of 4, which is hardly half of them, and the path does not come back to vertex 2 (else it would not be a tree). In the second tree, whether you choose 3 or 4, you have 2 edges on one side and 3 on the other. It is not surprising as it is hard to take one half of an odd number of edges. You must clarify your question. $\endgroup$
    – babou
    Mar 9, 2014 at 10:12
  • $\begingroup$ Given a vertex $v$ in a tree $T$, let $S_v$ be the set of subtrees formed by deleting $v$ and then adding it back to each component of the resulting forest (i.e., each element of $S_v$ is a subgraph of $T$ induced by $v$ and some component of $T-v$). It sounds like you want to find the vertex $v$ that minimizes $\min_{I\subseteq S_v}\left|\sum_{H\in I}|E(H)| - \sum_{H\in S_v\setminus I}|E(H)|\,\right|$. Is that correct? (The length of your edge traversal of each subtree would be exactly twice its number of edges.) $\endgroup$ Mar 10, 2014 at 8:49
  • $\begingroup$ @DavidRicherby I do not understand your definition. Maybe a notation standard I do not know. What kind of entities are $H$ and $E$? What is the definition of $E$? $I$ is an element of $S_v$, and thus is a tree. But H is defined as an element of $I$ and I am not sure in what way you consider $I$ to be a set. $\endgroup$
    – babou
    Mar 10, 2014 at 13:52
  • $\begingroup$ @babou $H$ is an element of $I$, which is a subset of (not element of) $S_v$, which is a set of induced subgraphs of $T$. So the graphs $H$ are induced subgraphs of $T$. For any graph $G$, $E(G)$ refers to the edge set -- that is standard notation. $\endgroup$ Mar 10, 2014 at 14:38
  • $\begingroup$ HOR2, welcome to CS.SE! Unfortunately, I'm afraid this question needs a lot of work. Those noun phrases are far too convoluted; I find them terribly painful to try to follow. I suggest you try breaking this down into some smaller bite-sized definitions, each building on the previous one, and then use them to give a clearer problem statement. Also, it would help to include an example, some intuition, the context where you ran into this, and your motivation. Finally: what have you tried on your own? $\endgroup$
    – D.W.
    Mar 11, 2014 at 23:47

2 Answers 2

1
$\begingroup$

For each vertex label each incident edge $e$ with the number of edges reachable through $e$ (including $e$).
The vertex you are looking for satisfies that the maximum of its labels is at most $\left\lceil\frac{n-1}2\right\rceil$. It is easily verified that there is exactly one such vertex in each tree. ($n$ denoes the number of vertices of the tree, thus $n-1$ is the number of edges.)

In order to find that vertex efficiently, we can modify depth first search.

We start at an arbitrary vertex and in each vertex we do the following:

  1. Initialize a flag candidate = true and an integer sum = 0.
  2. For each edge $e$ leading to a child $v$:
    1. Call the procedure on $v$. Denote the return value by $s$.
    2. Label the incident end of $e$ with $s$.
    3. sum = sum + s.
    4. If $s > \left\lceil\frac{n-1}2\right\rceil$ set candidate = false.
  3. Set $r = n - 1 - sum$.
  4. Label the incident end of the edge leading to the parent with $r$.
  5. If $r > \left\lceil\frac{n-1}2\right\rceil$ set candidate = false.
  6. If candidate == true the current vertex is the one we are looking for. Abort.
  7. return $r+1$.

The correctness should be straightforward. Since the additional effort is ${\cal O}(1)$ per vertex resp. per outgoing edge, the runtime stays in ${\cal O}(|V| + |E|) = {\cal O}(n)$.

$\endgroup$
1
  • $\begingroup$ @HOR2 and how can 2 be an answer in the first graph? $\endgroup$
    – babou
    Mar 9, 2014 at 11:11
1
$\begingroup$

Note: This is a rewriting of the previous version of my answer. It is hopefully easier to understand. The previous version had a bug in the vertex labeling formulae where it used $L_v(e)$ instead of $L^v(e)$.

Since the question was not clear, and changed over time, I present below a general method that can handle several different definition of a vertex to be identified by some property. I use it to compute both the Jordan center(s) and the "gravity" center(s).

From the initial statement of the question, and an erased comment made by the OP, it seemed that the problem was to find the Jordan Center(s) [there may be two], of the tree. The definition of the Jordan Center(s) states that it has minimal excentricity, the excentricity of a vertex being its longest distance to any other vertex. There may be one or two such vertices in a tree.

The current statement of the question, as clarified by David Richerby, seems to rather ask how to find what I am calling here the gravity center of the tree, i.e., a vertex where it can be divided into two subtrees such that the difference between their number of edges is minimal.

To simplify the presentation, here are some of the definitions and notations I am using.

  • a tree is a pair composed of a finite non-empty set of vertices (or nodes) and a set of unordered pairs of vertices, called edges, such that there is exactly one path between any two vertices. Our reference tree here is noted $T$.
  • an edge is said to be incident on each of its two vertices, and a vertex is said incident on all edges it belongs to. A vertex with a single incident edge is called a leaf.
  • a rooted-tree is a tree with a distinguished vertex $r$ called the root. To specify the root, it may be called a $r$-rooted-tree.
  • a rooted subtree of a tree $T$ is a rooted-tree such that all edges are edges in $T$, and all vertices except possibly the root have the same number of incident edges as in $T$. This means that the missing parts of $T$ must have been cut off at the root.
  • a rooted-tree is prime iff there is only one incident edge on the root.
  • a $u$-rooted subtree $s$ of a $v$-rooted tree $t$ is a daughter of $t$ iff (v,u) is an edge of $t$. Then, by adding the edge to the subtree $s$ you obtain a prime $v$-rooted subtree of $t$.
  • $D(t)$ is the set of daughters of a $v$-rooted tree $t$
  • $D(v)$ is the set of daughters of the full tree $T$ rooted in vertex $v$.
  • $E(t)$ is the set of edges in a (sub)tree $t$. For a vertex $v$, $E(v)$ is the set of incident vertices on $v$.
  • for a (sub)tree $t$, we call weight of $t$ its number of edges.
  • an attribute (characteristic value) of a rooted tree $t$ is said to be synthesized if it can be computed from the values of the same attribute for the daughters of $t$. The formula to be used to do this computation is called the synthesis formula. An initial attribute must be provided for all daughter subtrees that are only a single leaf vertex with no edge.
  • a vertex labeling formula for a tree $T$ is a formula that computes a label for each vertex $v$ from attributes computed for each daughter of the $v$-rooted tree $T_v$.

Note that the root of a daughter tree always has on less incident edge in the daughter than in the full tree. The missing edge is precisely the edge connecting it to the root of its parent tree.

Synthesized attributes can be computed for a $v$-rooted tree $t$ by a recursive function calling itself recursively on each of the daughters of $t$.

Alternatively, it can be computed for all daughters of all rooted subtrees of $T$. There are exactly two such daughters for each edge of $T$, one at each end of the edge. One proceeds by initializing all the leaf vertex attributes, and then using the synthesis formula to compute the attribute for all daughter trees, when their own daughter have had their attribute computed. It is easy to show that, as long as there is a daughter without its attribute, there is one where the attribute can be computed because it has been done for all its daughters. Hence the algorithm terminates, with every daughter having its attribute computed.

Various optimizations are possible, depending on what is being computed.

Case of the Jordan center.

The attribute needed is the depth $\phi$ of each daughter tree, i.e., the length of longest path starting from its root.

We initialize the attribute $\phi(l)$ of each leaf daughter $l$ to 0, since there is no path starting from it.

The synthesis formula to compute the attribute for a daughter $d$ is $\phi(d)= 1+{Max}_{t\in D(d)} \phi(t)$

The vertex labelling formula is then: $L(v)=\max_{t\in D(v)} \phi(t)$

The Jordan centers are the vertices with the smallest label.

Case of the gravity center

We want to find a vertex $g$ such that the tree can be split at that vertex (keeping a copy of the vertex in each of the two parts) so that the weight difference between the two parts is minimal, the weigth of a tree being the number of edges. I am calling such a vertex a gravity center of the tree (there may be 2 gravity centers).

This amounts to finding a vertex $g$ minimizing the weight difference between the two partitions of a bipartioning of $D(g)$.

For this purpose we choose as attribute the weight $\omega(d)$ of each daughter tree.

We initialise the attribute $\omega(l)$ of each leaf daughter $l$ to 0, since it contains no edge.

The synthesis formula to compute the attribute for a daughter $d$ is $\omega(d)=\Sigma_{t\in D(v)} 1+\omega(t)$

Note that, as soon as there is an edge (u,v) such that the two daughter corresponding to that edge have their weight computed, their sum is the weight $p=|E(T)|$ of the whole tree $T$. This can then be used to simplify computation and speed up the algorithm.

The vertex labeling formula label each vertex $v$ with the smallest weight difference $\delta_v$ between two subtrees partitioned on that vertex. The vertex with the smallest such value $\delta_v$ is the answer to the question. The vertex labelling formula is then: $L(v)=\min_{I\subseteq D(v)}\left|\sum_{t\in I}\omega(t) - \sum_{t\in D(v)\setminus I}\omega(t)\,\right|$.

Then the gravity center is the vertex with the smallest label.

However, this vertex labeling function is NP complete in the number of incident edges on the vertex, as it is a Partition problem. We need a better way to identifies the center of gravity, without actually computing the partition into 2 subtrees.

Instead, we identify the gravity center with another property: a vertex $g$ is a gravity center iff no prime $g$-rooted subtree has more than $(p+1)/2$ edges, where $p=|E(T)|$ is the total number of edges. Hence it is a vertex $g$ with the smallest maximum value for the weight of a prime $g$-rooted subtrees. Since the weight of a prime $g$-rooted subtree, is just 1 more than the weight of the corresponding daughter, we can use instead the weight of daughters.

Thus we use the following vertex labelling formula: $L(v)=\max_{t\in D(v)} \omega(t)$
Any vertex $g$ with the smallest label $L(g)$ is a gravity center.

Sketch of a Proof

First we note there may be one or two gravity centers. For example, if you connect two trees having the same weight (number of edges) with an additional edge, then the vertices joined by that edge are the two gravity center of the larger tree thus created. They both have a minimum weight difference equal to 1 (corresponding to the connecting edge). So they both have a prime rooted subtree with $(p+1)/2$ edges. It is the rooted subtree that start with the connecting edge.

We note $\delta_v$ the minimum weight difference between subtrees of a bipartition rooted at the vertex $v$.

Then, we prove that if a prime $v$-rooted subtree $\tau$ has more than $(p+1)/2$ edges, there is another vertex $u$ such that $\delta_u<\delta_v$, so that $v$ cannot be a gravity center. The vertex $u$ is the vertex at the other end of the root vertex of $\tau$. The proof uses the fact that the total weight of all prime $v$-rooted subtree is constant, equal to $p=|E(T)|$.

We then prove that if a vertex $g$ has a prime $g$-rooted subtree with exactly $(p+1)/2$ edges, then there is another such vertex, but all other vertices have a prime $g$-rooted subtree with more edges.

Similarly we prove that if a vertex $g$ has all prime $g$-rooted subtree with less $(p+1)/2$ edges, all other vertices have a prime $g$-rooted subtree with more than $(p+1)/2$ edges.

The last 2 proofs are by finite induction on the distance between the gravity center and the vertex considered. One can show that on a path from a gravity center (that does not include the other, if any), the difference $\delta_v$ associated with a vertex $v$ increases strictly with the distance of $v$ from the gravity center. One can also prove that the maximum weight of a prime $v$-rooted subtree increases strictly too in the same way. This can be used to find quickly the gravity center.

$\endgroup$
12
  • $\begingroup$ thanks! but no. i don't want to find jordan center. i was wrong. $\endgroup$
    – HsnVahedi
    Mar 10, 2014 at 5:46
  • $\begingroup$ @HOR2 Then can you better explain what you want. Your first example cuts the graph into 4 subgraph. You should say what thye subsets of edges can be in this example. Anyway, as I said, you can use the same technique to compute the center with respect to whatever property of subtrees. You can replace depth of rooted subtrees by their number of edges. You only have to change the propagation formula. $\endgroup$
    – babou
    Mar 10, 2014 at 8:06
  • $\begingroup$ @DavidRicherby I regret your edit. Yhe problem was poorly stated, and the question was changed after I gave my answer. Both examples given then gave the jordan center as answer, and the OP himself suggested it might be what he was looking for. No I get a downvote because the question was changed under my feet. $\endgroup$
    – babou
    Mar 10, 2014 at 8:21
  • $\begingroup$ @babou I edited your first paragraph because, whether you intended it or not, it came across as extremely rude to the asker. This is not the first time so please try to be more careful about that. The question changed only by the removal of an example, and, while I agree that the question is somewhat unclear, its meaning didn't change in the edit. So, the Jordan centre was not relevant to the original question, either. If the correct answer to the original example was the Jordan centre (I didn't check), that seems to have been a coincidence. $\endgroup$ Mar 10, 2014 at 8:38
  • $\begingroup$ You are right! My first explanation was a disaster. $\endgroup$
    – HsnVahedi
    Mar 10, 2014 at 9:17

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