Hardness and inapproximability results for minimum verification set and minimum path decision tree problems

Türker, Uraz Cengiz and Yenigün, Hüsnü (2012) Hardness and inapproximability results for minimum verification set and minimum path decision tree problems. [Working Paper / Technical Report] Sabanci University ID:10.5900/SU_FENS_WP.2012.19826

[thumbnail of Manuscript] PDF (Manuscript)
MinVS-TechRep.pdf

Download (322kB)

Abstract

Minimization of decision trees is a well studied problem. In this work, we introduce two new problems related to minimization of decision trees. The problems are called minimum verification set (MinVS) and minimum path decision tree (MinPathDT) problems. Decision tree problems ask the question "What is the unknown given object?". MinVS problem on the other hand asks the question "Is the unknown object z?", for a given object z. Hence it is not an identification, but rather a verification problem. MinPathDT problem aims to construct a decision tree where only the cost of the root-to-leaf path corresponding to a given object is minimized, whereas decision tree problems in general try to minimize the overall cost of decision trees considering all the objects. Therefore, MinVS and MinPathDT are seemingly easier problems. However, in this work we prove that MinVS and MinPathDT problems are both NP-complete and cannot be approximated within a factor in o(lg n) unless P = NP.
Item Type: Working Paper / Technical Report
Subjects: Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Q Science > QA Mathematics > QA076 Computer software
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Hüsnü Yenigün
Date Deposited: 22 Oct 2012 16:42
Last Modified: 26 Apr 2022 10:50
URI: https://research.sabanciuniv.edu/id/eprint/19826

Actions (login required)

View Item
View Item