ISSN:
1435-5914
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. The ℱ Hypergraph Sandwich Problem (ℱHSP) is introduced here as follows: Given two hypergraphs H 1=(X,ℰ1) and H 2=(X,ℰ2) where ℰ1={E 1 1,…,E m 1}, ℰ2={E 1 2,…,E m 2} and E i 1⊆E i 2 for all 1≤i≤m, is there a hypergraph H=(X,ℰ) with ℰ={E 1,…,E m } such that E i 1⊆E i ⊆E i 2 for all 1≤i≤m which belongs to a specified hypergraph family ℱ? Hypergraph sandwich problems for several properties studied here occur in a variety of important applications. We prove the NP-completeness of the Interval HSP and the Circular-arc HSP. This corresponds to the problem of deciding whether a partially specified (0,1)-valued matrix can be filled in such that the resulting 0/1 matrix has the consecutive ones property, (resp., circular ones property). The consecutive ones property arises in databases and in DNA physical mapping. Further results shown are a set of conditions relating interval hypergraphs with acyclic hypergraphs. Finally, the k-tree graph sandwich problem is studied. The general problem is shown to be NP-complete and the fixed k version is given a polynomial algorithm. Both problems are based on solutions to the corresponding partial k-tree recognition problems.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s003730050028
Permalink
