Browse Prior Art Database

The Complexity of Identifying Redundant and Essential Elements

IP.com Disclosure Number: IPCOM000128556D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 8 page(s) / 28K

Publishing Venue

Software Patent Institute

Related People

Shlomo Moran: AUTHOR [+3]

Abstract

In many optimization problems a solution is a subset of optimum number of elements satisfying some desired property. An element is redundant if it does not belong to any solution of the problem. An element is essential if it belongs to every solution of the problem. We consider the complexity of indenti:Eying redundant and essential elements in a sample of NP-Hard optimization problems. It is shown that these identification problems are also NP-Bard. The proofs are based on an analysis of the original reductions of Cook [3] and Karp [4], 1

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 16% of the total text.

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

The Complexity of Identifying Redundant and Essential Elements

by Shlomo Moran and Yehoshua Perl*

Computer Science Department

136 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 Technical Report 79-26 November 1979 *Department of Mathematics and Computer Science Bar Ilan University, Ramat Gan, Israel

Cover design courtesy of Ruth and Jay Leavitt.

The Complexity of Identifying Redundant and Essential Elements

by Shlomo Moran and Yehoshua Perl

Abstract

In many optimization problems a solution is a subset of optimum number of elements satisfying some desired property. An element is redundant if it does not belong to any solution of the problem. An element is essential if it belongs to every solution of the problem.

We consider the complexity of indenti:Eying redundant and essential elements in a sample of NP-Hard optimization problems. It is shown that these identification problems are also NP-Bard. The proofs are based on an analysis of the original reductions of Cook [3] and Karp [4],

1. Introduction

In many optimization problems a solution is a subset of optimum number of elements satisfying desired property. Two examples are the minimum set cover problem and the maximum clique problem [Ka] (formal definitions are given in the next section). In the minimum set cover problem the subsets S1, S2,..., Sn of a set A are the elements of the problem, and in the maximum clique problem the vertices of a graph G = (V,E) are the elements of the problem. These two optimization problems, as many others, are NP-Hard, since the corresponding decision problems are NP-Complete [4].

A possible approach in treating such a difficult problem is reducing the given problem to a problem of less elements. An element is redundant if it does not belong to any solution of the problem. An element is essential if it belongs to every solution of the problem. Clearly such an optimization problem can be reduced by eliminating the redundant elements. The problem can be further reduced, using the information about the essential elements. If, for example, Sj=A is an essential subset in a minimum set cover problem then the reduced problem is finding a minimum cover of A-S i by the subsets Sj, j # i. Or if a vertex v is an essential vertex in a maximum clique problem then the reduced problem is finding a maximum clique in the induced subgraph of the neighbors of v.

University of Minnesota Page 1 Dec 31, 1979

Page 2 of 8

The Complexity of Identifying Redundant and Essential Elements

Such an approach is used in Switching Theory in minimization of switching functions by the Quine-McCluskey method [6]. Our work was motivated by a recent work of Chueka and Goldberg [2]. They apply the minimum set cover problem in automatic text: analysis [7] to identify the relevant meanings of the words in the text out of the possible meanings of a word given in a dictionary.

In this wor...