On why is it the case that finding maximal contained plans with disjunctive sources is NP-hard

[Subbarao Kambhampati <rao@asu.edu>]

Mark asked for an intuitive reason as to why finding a maximally contained 
plan in the presence of disjunctive sources is NP-hard. Here is a short PDF 
file, taken from Oliver Duschka's thesis (this is the guy who did the work 
on inverted rules algorithm, as well as the complexity work) that comes 
reasonably close to an "example-based" explanation (look, in particular, at 
the example in the second page--that shows a nice way of proving 
NP-hardness--basically there they show that
graph 3-colorability needs to be used to generate a maximally contained 
plan, and since the former is NP-hard, so is the latter).

Rao

ps: If you read it, then consider the following question (which explains 
the strange venn-diagram-like figures in the bottom of the complexity 
slide)  IN the example 1, the source v is a disjunctive source that contains
(a) all UA flights (b) all SW flights (c) all flights going through SFO 
(this is why it is disjunctive). Here is a way you could make the source 
"conjunctive"--just say "it has all flights on all airlines". If we do 
this, then the source description will be conjunctive. Yes, the description 
will be an "exaggeration"--in that the source will not really be giving all 
the flights, but then it is not like the original disjunctive description 
is definitely not exaggerating (afterall, we see descriptions as 
"advertisements" rather than tight guarantees). What this shows you is that 
you can reduce the complexity of reformulation by operating with "loose" 
source descriptions. The question that you should ponder--if you feel like 
pondering at this hour of the day--is what gives? What are  you losing by 
going with this looser description?

Attachment: disj-sources.PDF
Description: Adobe PDF document