Solving the Target-Value Search Problem

Proceedings of the International Symposium on Combinatorial Search, 7

Volume

Vol. 7 No. 1 (2014): Seventh Annual Symposium on Combinatorial Search

Research Abstracts

This paper addresses the Target-Value Search (TVS) problem, which is the problem of finding a path between two nodes in a graph whose cost is as close as possible to a given target value, T. This problem has been previously addressed: first, for directed acyclic graphs; second, for general graphs under the assumption that nodes can be revisited given that the same edge can not be traversed twice. In this work we focus on a more restrictive variant of the same problem where nodes can not be revisited. We prove that this variant is NP-complete and discuss novel theoretical properties and provide empirical results to solve this problem optimally.

10.1609/socs.v5i1.18335