انجمن کامپیوتر ایران

یک -t پوشش هندسی (1<t) برای گراف هم‌بند هندسی G، زیرگراف پوشای G' برای G است؛ به طوری که فاصله‌ی بین هر جفت از راس‌ها در G'، حداکثر t برابر فاصله‌‌شان در G است. یک مجموعه نقطه نادقیق D، با دیسک‌هایی دوبه‌دو جدا از هم در صفحه مدل می‌شود. اگر از هر دیسک D یک نقطه انتخاب شود؛ آن‌گاه مجموعه‌ی حاصل یک نمونه‌ی دقیق از D است. گراف G=(D,E) برای مجموعه نقطه نادقیق D، یک گراف هندسی نادقیق است؛ که E یک مجموعه از جفت‌دیسک‌های نامرتب در D است. برای نمونه‌ی دقیق S از D، گراف G_S=(S,E_S) نمونه‌ی دقیق G متناظر با S است؛ که E_S مجموعه یال‌های E متناظر با S است. در این مقاله نشان می‌دهیم که برای یک گراف هندسی نادقیق G=(D,E)، یافتن نمونه دقیق S از D به طوری که G_S=(S,E_S) شامل یک -tپوشش با حداکثر m یال است، یک مسئله‌ی -NP سخت است.