One of my algorithms profs was fond of saying that if you find yourself faced with an NP complete problem, you're probably solving the wrong problem. In other words, usually you're dealing with a polynomial special case of what you think is the actual problem. Just FYI -- I haven't digested your enormous post yet...