Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site utcsri.UUCP
Path: utzoo!utcsri!wagner
From: wagner@utcsri.UUCP (Alan Wagner)
Newsgroups: comp.arch
Subject: Re: Hypercube (partitioning)
Message-ID: <4348@utcsri.UUCP>
Date: Wed, 11-Mar-87 14:01:06 EST
Article-I.D.: utcsri.4348
Posted: Wed Mar 11 14:01:06 1987
Date-Received: Wed, 11-Mar-87 21:25:17 EST
References: <3312@osu-eddie.UUCP> <633@ames.UUCP>
Reply-To: wagner@utcsri.UUCP (Alan Wagner)
Organization: CSRI, University of Toronto
Lines: 51
Summary: 

In article <3312@osu-eddie.UUCP> lien@osu-eddie.UUCP writes:
>>From: Yao-Nan Lien <lien>
>>
>>Definately, there is a problem of partitioning the problem to be
>>solved into many subtasks and mapping these tasks to the real
>>processors. The major concern is to balance the processor
>>utilization and to minimize the possible communication among
>>processors.
>>-- Yao-Nan Lien

>A paper was written some time ago about the general partitioning
>problem.  It's NP-complete.  Not trivial.

To follow up on Eugene's remarks, trying to map processes to processors
so that only neighbour to neighbour communication is required is the
subgraph isomorphism problem (NP-complete, see Garey&Johnson) see also

S.H. Bokhari, On the Mapping Problem, IEEE Trans. on Computers,
C-30, 3 , March 1981.

More specifically if we restrict the host to a hypercube (i.e. Determine
if a graph is a partial subgraph of hypercube of some dimension n) then
the problem remains NP-complete
 
F. Afrati and C. H. Papadimitriou and G. Papageorgiou,
The Complexity of Cubical Graphs,
Eleventh Intl. Colloquium on Automata, Languages and Programming, 1984,
 
G. Cybenko, D.W. Krumme and K.N. Venkataraman,
Hypercube Embedding is NP-complete,
Dept. of Computer Science, Tufts University, Medford August 1985

And more recently even when the source graph is a tree (i.e Given a tree
T and integer k is T a subgraph of a cube of size k.) the problem is
is still NP-complete.

A. Wagner and D. Corneil,  Embedding Trees in a Hypercube is NP-complete,
Tech Report #197/87
University of Toronto, Toronto, Can.

With respect to trees,  an interesting conjecture concerning binary trees 
mentioned in 

S.N. Bhatt,  F.R.K. Chung, T.Leighton and  A.L. Rosenberg,
Optimal Simulations of Tree Machines,
Proceedings of the 27th FOCS Symposium, 1985

is that "Are all binary trees with 2^n nodes a subgraph of a cube of size
n+1?".

													Alan Wagner