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

PDF (Manuscript)

MinVS-TechRep.pdf

Download (322kB)

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 |