od beaver » 1. 1. 2008 13:54
Tak vezmeme si problem HK na obycejnem grafu G. To co bych chtel je, ze tuhle HK umim (polynomialne) prevest na HK pro nadkubicke grafy (tim ukazu, ze HK pro nadkubicke grafy je NPU problem, protoze obyc HK je taky NPU).
Rekneme, ze v G nejsou vrcholy se stupnem 1 (nebo mensim). Kdyby byly, pak tam nemuze HK existovat a umim ji vyloucit v polynomialnim case (coz pro nas neni vubec zajimave). Zaroven predpokladejme, ze zadny vrchol G neobsahuje smycku (tzn. hranu (v, v) pro nejake v). Kdyby graf smycky obsahoval, muzeme je beztrestne odstranit (HK to nijak neublizi).
Vsechny vrcholy v G maji ted stupen 2, nebo vetsi a neobsahuji smycky. Hurra - tak si tam ty smycky pridame (pro kazdy vrchol v, pridame hranu (v,v)). Pokud bereme neorientovane grafy, pak je stupen vsech vrcholu alespon 4.
Takze prevod tam uz mame a prevod zpet je taky jednoduchy - jen zahodime smycky. A to, ze jsou oba prevody polynomialni, je doufam videt.
Tak vezmeme si problem HK na obycejnem grafu G. To co bych chtel je, ze tuhle HK umim (polynomialne) prevest na HK pro nadkubicke grafy (tim ukazu, ze HK pro nadkubicke grafy je NPU problem, protoze obyc HK je taky NPU).
Rekneme, ze v G nejsou vrcholy se stupnem 1 (nebo mensim). Kdyby byly, pak tam nemuze HK existovat a umim ji vyloucit v polynomialnim case (coz pro nas neni vubec zajimave). Zaroven predpokladejme, ze zadny vrchol G neobsahuje smycku (tzn. hranu (v, v) pro nejake v). Kdyby graf smycky obsahoval, muzeme je beztrestne odstranit (HK to nijak neublizi).
Vsechny vrcholy v G maji ted stupen 2, nebo vetsi a neobsahuji smycky. Hurra - tak si tam ty smycky pridame (pro kazdy vrchol v, pridame hranu (v,v)). Pokud bereme neorientovane grafy, pak je stupen vsech vrcholu alespon 4.
Takze prevod tam uz mame a prevod zpet je taky jednoduchy - jen zahodime smycky. A to, ze jsou oba prevody polynomialni, je doufam videt. :D