The binary identification problem for weighted trees

The Binary Identification Problem for weighted trees asks for the minimum cost strategy (decision tree) for identifying a vertex in an edge weighted tree via testing edges. Each edge has assigned a different cost, to be paid for testing it. Testing an edge e reveals in which component of T − e lies the vertex to be identified. We give a complete characterization of the computational complexity of this problem with respect to both tree diameter and degree. In particular, we show that it is strongly NP-hard to compute a minimum cost decision tree for weighted trees of diameter at least 6, and for trees having degree three or more. For trees of diameter five or less, we give a polynomial time algorithm. Moreover, for the degree 2 case, we significantly improve the straightforward O ( n 3 ) dynamic programming approach, and provide an O ( n 2 ) time algorithm. Finally, this work contains the first approximate decision tree construction algorithm that breaks the barrier of factor log n.

Authors

• Ferdinando Cicalese
• Tobias Jacobs
• Eduardo Laber
• Caio Valentim

Keywords

No keywords are indexed for this paper.