مقاله الگوریتم‌ها و پیچیدگی برای پوشش‌های مسیر DAGهای زمانی: Dilworth چه زمانی پویا است؟

چکیده

In this paper, we study a dynamic analogue of the Path Cover problem, which can be solved in polynomial-time in directed acyclic graphs. A temporal digraph has an arc set that changes over discrete time-steps, if the underlying digraph (the union of all the arc sets) is acyclic, then we have a temporal DAG. A temporal path is a directed path in the underlying digraph, such that the time-steps of arcs are strictly increasing along the path. Two temporal paths are temporally disjoint if they do not occupy any vertex at the same time. A temporal (resp. temporally disjoint) path cover is a collection of (resp. temporally disjoint) temporal paths that covers all vertices. In this paper, we study the computational complexities of the problems of finding a temporal (disjoint) path cover with minimum cardinality, denoted as Temporal Path Cover (TPC) and Temporally Disjoint Path Cover (TD-PC). We show that both problems are NP-hard even when the underlying DAG is planar, bipartite, subcubic, and there are only two arc-disjoint time-steps. Moreover, TD-PC remains NP-hard even on temporal oriented trees. In contrast, we show that TPC is polynomial-time solvable on temporal oriented trees by a reduction to Clique Cover for (static undirected) weakly chordal graphs (a subclass of perfect graphs for which Clique Cover admits an efficient algorithm). This highlights an interesting algorithmic difference between the two problems. Although it is NP-hard on temporal oriented trees, TD-PC becomes polynomial-time solvable on temporal oriented lines and temporal rooted directed trees. We also show that TPC (resp. TD-PC) admits an XP (resp. FPT) time algorithm with respect to parameter tmax + tw, where tmax is the maximum time-step, and tw is the treewidth of the underlying static undirected graph.

چکیده به فارسی (ترجمه ماشینی)

در این مقاله ، ما یک آنالوگ پویا از مشکل پوشش مسیر را مطالعه می کنیم ، که می تواند در زمان چند جمله ای در نمودارهای اسکلی به کارگردانی حل شود.Digraph موقتی دارای یک قوس است که بر روی مرحله زمانی گسسته تغییر می کند ، اگر Digraph زیرین (اتحاد همه مجموعه های قوس) acyclic باشد ، پس ما یک DAG موقتی داریم.یک مسیر زمانی یک مسیر کارگردانی در Digraph زیرین است ، به گونه ای که مرحله زمانی قوس ها به شدت در طول مسیر در حال افزایش است.اگر در همان زمان هیچ راس را اشغال نکنند ، دو مسیر موقتی به طور موقت از هم جدا می شوند.یک پوشش مسیری زمانی (به ترتیب از هم جدا شدن) مجموعه ای از مسیرهای زمانی (به ترتیب جداگانه) است که تمام راس ها را در بر می گیرد.در این مقاله ، ما پیچیدگی های محاسباتی مشکلات یافتن یک پوشش مسیر زمانی (جدا) با حداقل کاردینال بودن ، که به عنوان پوشش مسیر زمانی (TPC) و پوشش مسیر زمانی جدا شده (TD-PC) مشخص می شود ، بررسی می کنیم.ما نشان می دهیم که هر دو مشکل NP سخت هستند حتی وقتی که DAG زیرین مسطح ، دو طرفه ، زیرمجموعه است و فقط دو مرحله از زمان قوس دیزاین وجود دارد.علاوه بر این ، TD-PC حتی در درختان متمرکز زمانی NP باقی مانده است.در مقابل ، ما نشان می دهیم که TPC با کاهش پوشش به صورت کلیپ برای نمودارهای وتر ضعیف (استاتیک غیر مستقیم) (یک زیر کلاس از نمودارهای کامل که برای آن پوشش Clique یک الگوریتم کارآمد را پذیرفته است) بر روی درختان محور زمانی قابل حل است.این تفاوت الگوریتمی جالب بین دو مشکل را برجسته می کند.اگرچه در درختان محور زمانی NP سخت است ، TD-PC در خطوط محور زمانی و درختان هدایت شده زمانی قابل حل است.ما همچنین نشان می دهیم که TPC (به ترتیب TD-PC) یک الگوریتم زمان XP (به ترتیب FPT) را با توجه به پارامتر TMAX + TW ، که در آن TMAX حداکثر مرحله زمان است ، می پذیرد و TW پهنای درخت نمودار استاتیک زیرین است.بشر