Global Methods for Combinatorial Isoperimetric Problems
With a focus on global methods, this innovative text employs morphisms to transform new problems into more restricted and easily solvable settings while preserving essential structure.
TABLE OF CONTENTS Global Methods for Combinatorial Isoperimetric Problems
Chapter 9: Morphisms for MWI Problems
In Chapter 6, Section 6.2 we observed that for graphs having nested solutions for EIP, compression reduces the EIP on their product to a maximum weight ideal (MWI) problem on its compressibility order. Also, stabilization on the graph of any regular solid reduces both its EIP and VIP to MWI problems (on its stability order, but with different weights). The MWI problem, like the EIP and VIP, is NP-complete (see Section 6.2 of Chapter 6), but now we show that it has its own notion of morphism. MWI-morphisms extend, but are qualitatively different from, Steiner operations for EIP and VIP, in that the underlying functions may be many-one. They represent a divide-and-conquer strategy for solving MWI problems, but unlike the elementary applications of divide-and-conquer to sorting, etc. one must divide cleverly in order to conquer.
9.1 MWI-Morphisms
9.1.1 Quotients
If P and Q are weighted posets and ? : P ? Q a (many-one) onto function from which we hope to get a morphism for the MWI problem, what properties must it have? As in our previous considerations of this basic question, it must preserve the structures which define the MWI problem, i.e.
-
Partial order: x ? y implies ? ( x) ? ? ( y);
-
Weights: ? x ? Q, x = ? ? 1 ( x) defines a cardinality function , , on Q. Also, ? x ? Q
Copyright Cambridge University Press 2004 under license agreement with Books24x7
