کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420506 | 683951 | 2008 | 6 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The minimum spanning strong subdigraph problem is fixed parameter tractable The minimum spanning strong subdigraph problem is fixed parameter tractable](/preview/png/420506.png)
A digraph DD is strong if it contains a directed path from xx to yy for every choice of vertices x,yx,y in DD. We consider the problem (MSSS) of finding the minimum number of arcs in a spanning strong subdigraph of a strong digraph. It is easy to see that every strong digraph DD on nn vertices contains a spanning strong subdigraph on at most 2n−22n−2 arcs. By reformulating the MSSS problem into the equivalent problem of finding the largest positive integer k≤n−2k≤n−2 so that DD contains a spanning strong subdigraph with at most 2n−2−k2n−2−k arcs, we obtain a problem which we prove is fixed parameter tractable. Namely, we prove that there exists an O(f(k)nc)O(f(k)nc) algorithm for deciding whether a given strong digraph DD on nn vertices contains a spanning strong subdigraph with at most 2n−2−k2n−2−k arcs.We furthermore prove that if k≥1k≥1 and DD has no cut vertex then it has a kernel of order at most (2k−1)2(2k−1)2. We finally discuss related problems and conjectures.
Journal: Discrete Applied Mathematics - Volume 156, Issue 15, 6 August 2008, Pages 2924–2929