Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a labeled forest B and a labeled input forest I. All nodes in I exists in B (opposite may not be true).

I have a feeling for what I want to accomplish, I want to trust all reachables in the input forest I and add those edges from B if it does not violate the reachables. For example:

Forest B           Forest I                        

    A              A
     B              G
     C             D   
      I             H  
    D                C   
     E
      F               
      G              
       H             

Heuristic output (intuition):
    A
     B
     G
    D
     E
      F
      H
       C
        I

I would like to formulate the problem so that it is well defined. I am not so confident with defining a problem (in my studies most of the times the aim was to solve a well defined problem and fewer times it was to make something vague a well defined problem). I would like to reach out for help, to see if there are any mistakes that could be spotted, or if perhaps I could write the problem formulation in a clearer way. Any help is much appreciated.

Problem formulation (attempt)

Given: A labeled directed forest G and a labeled directed input forest I is given. All nodes in I also exists in G. The direction is from node to parent

Produce: an output forest O such that:

  1. For all u,v in I, if.f u can reach v in I then u can reach v in O
  2. An edge (x,y) in B is in O if.f it can be merged with I to form a forest T for which the following is true: for all u,v in I, if.f u can reach v in I then u can reach v in T. Forest T consist of edges in I except any for node x and edge (x,y).
  3. edges in B that are not in O are used to add additional edges: let e=(x,y) be an edge in B but not in O, so it must violate 2. if a exist such that (x,a) does not violate 2, and a is an ancestor to y, then that (x,a) which has a nearest to y is in O
  4. All nodes in B are also in O

Nr 3. can also be stated recursively, for any e=(x,y) in B that violates 2 step1: if e does not violate 2 then add it to O (next e). Otherwise goto step2 step2: if y does not have a parent - done (next e). Otherwise, let v be the parent of y and let e=(x,v), go to step1.

I believe only unique solutions are possible, let $O_1$ and $O_2$ be two solutions to the same problem. If they differ in number of nodes then one violates 4. If they differ in number of edges then one must have extra edges which did not violate 1 or 2, or it came from 3, but any such edge must have also been given to the other solution so they must have the same number of edges. If an edge exist in one solution but not the other, then for sure it can not come from G or I or else it would be in both solutions. So it must have been created to fulfill nr 3, and so there must be an ancestor which does not violate 1 or 2. But since it is a forest the nearest ancestor is always the same, so the edge can not differ. So all edges must be the same.

I also believe there always exist a solution, 1,2 and 3 is easy to show that an $O$ exist for, just add the edges which are allowed. For number 4, if a node was not added from G then it must be because its edge was violating some edge in I, and so that node must have been added by some edge in I, so no nodes can be missing.

Question

Is the problem formulation well defined? Are there weak spots in either my reasoning or the problem formulation?

Could I rephrase myself to make it clearer? In particular nr 3 is a bit cumbersome.

Thanks in advance.

share|improve this question
1  
A minor note: A graph that consists of a disjoint set of trees is called a "forest". –  ESultanik May 10 '11 at 20:13
    
Thanks I'll update. –  j-a May 10 '11 at 20:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.