I'm definitely not a math expert so please forgive me in advance for not using the proper vocabulary or conventions. I'm kind of stuck with the following situation in a project of mine:
I have been given a dataset which I found more convenient to represent as an oriented graph (or "polytree"), such as the one given below.
Computing each path of the graph returns me a value, and the only assumption we can be sure about is that the value returned by computing a prefix of a given path always return a value below or equal to computing the full path. For instance :
$$f((A,D)) \leqslant f((A,D,G)) \leqslant f((A,D,G,I))$$
My objective here is to minimize the maximum value returned by the paths of the tree by deleting the lowest amount of edges possible.
As an example, let $S$ be a set all the maximum paths of the graph given above: $$S = \{ (A,C),(A,D,F),(A,D,G,I),(B,D,F),(B,D,G,I),(B,E),(H,I) \}$$
... and let's assume the maximum value returned by the computation of all these is returned by $f(B,D,F)$ : $$max(S) = f((B,D,F)) = 5$$
"Deleting" the edge between D and F would give us a new set of paths $S'$ :
$$S = \{ (A,C),(A,D,F),(A,D,G,I),(B,D,G,I),(B,E),(H,I) \}$$
of which the maximum value is now given by :
$$max(S') = f((A,D,G,I)) = 1$$
... which we believe to be a significant improvement in our system. Trivially, deleting every edge of the graph would result in returning the smallest value possible; yet this would not be considered as a good improvement, in regards of the number deleted edges.
For the moment, I'm kind of solving this problem by computing every possible combinations of edges in the tree, and comparing the result to hard-coded threshold values; which is obviously computational-heavy.
My questions include:
- How to solve the problem of deleting edges, other than adopting a brute-force approach, by taking advantage of network graph theories I'm definitely not familiar with ?
- How to adopt a more "natural/human" decision over the number of edges deletions vs. minimizing the returned value of the tree ?
In addition, I'm very eager to learn more about this, yet failed to find any advanced references/courses; so please don't hesitate to throw documentation in this regard you may know about, this would be highly appreciated!
Thank you,
Edit May 7, 2018
Regarding $f$, its output is directly related to the values of each node composing a path: Each node actually consists in a python dictionary-like structure. With $A$ and $C$ denoting two nodes in the graph above:
$$ \forall x \in \mathbb{N}; \forall \delta, \gamma \in [0,1] $$
$$ \mathrm{A}(x)=\begin{cases} 7 & \text{if }x=1\\ 2 & \text{if }x=2\\ \epsilon & \text{otherwise} \end{cases} $$ $$ \mathrm{C}(x)=\begin{cases} 5 & \text{if }x=1\\ 3 & \text{if }x=2\\ \epsilon & \text{otherwise} \end{cases} $$
For the sake of the example, I guess we could simplify $f$ as:
$$f((A,C)) = \delta \times \max_{ x = 1 }(A,C) + \gamma \times \max_{ x = 2 }( A(2), C(2) )$$
(Though as stated above, $f$ is unknown and may vary depending on the information we're mining in the graph)
Maybe you already solved this but let me offer a thought or two.
So if $P\in G$ denotes some path in a poly-tree/directed graph, you seem to want something like minimizing this energy: $$ \mathcal{E}(G) = \min_{E} \;\max_{P\in G \setminus E} \;f(P) + \beta \,|E| $$ where $E$ is the set of edges you would like to delete, $|E|$ is the size of $E$, and $\beta$ is the weight of the penalty for deleting an edge.
Brute force minimization of this for fixed $\beta$ would entail iterating over different $E$ sets and computing $\mathcal{E}$ each time, and taking the lowest one.
How can we make this faster? This optimization seems like a minimax game to me, so maybe you can repurpose alpha-beta pruning to work here.
You haven't said much about $f$. For instance, whether it could be computed or even approximated by some kind of max flow (i.e. sum of weights on the edges). I'll have to think more about using the "metric-space-like" property of subpaths that you mentioned. But I think knowing that might help you get some alpha-beta-pruning-like theoretical guarantrees.