I have a directed acyclic graph $G=(V,E)$ where each vertex $v$ is associated with a weight $w_v$ such that $$w_v=1+\sum\limits_{(v,v')\in E} w_{v'}$$ and $w_v=1$ in case $v$ is a leaf.

I am trying to construct $G$ and the weights or at least the weights. The information that is available to the system can be anything useful for starting the construction. Though one interesting information is of type $v$ is a possible ancestor of $v'$. I am interested in similar problems exists in the literature for further reading and understanding. Appreciate any pointers.

  • $\begingroup$ What is the input and what is the required output? Can you make your question more concrete? $\endgroup$ – Yuval Filmus Aug 8 '19 at 23:07
  • $\begingroup$ @YuvalFilmus I am given information of the form “v is a possible ancestor of v’” or “v is not a possible ancestor of v’” for any two vertices v and v’ the system choose. and I am asked to recover G using smallest number of information. $\endgroup$ – seteropere Aug 8 '19 at 23:15
  • $\begingroup$ What happens if you are given that "$x$ is a possible ancestor of $y$" for all pairs $x,y$? $\endgroup$ – Yuval Filmus Aug 8 '19 at 23:37
  • $\begingroup$ @YuvalFilmus I have a hidden DAG with bounded indegree. I am trying to reveal it with edge-detection queries. The literature shows asymptotic bounds for general classes but I am interested in finding the minimum queries for graphs with indegree at most one. I thought learning weights will be more general setting and applicable to more audience. But seems mistaken. $\endgroup$ – seteropere Aug 8 '19 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.