کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430225 | 687929 | 2014 | 20 صفحه PDF | دانلود رایگان |
• We derive fixed-parameter algorithms for a generalization of above-guarantee Max-Cut.
• The generalization also captures properties of oriented/edge-labelled graphs.
• Our results build on and generalize the work of Crowston et al. (ICALP 2012) on Max-Cut.
• As a corollary we solve an open question of Raman and Saurabh (Theor. Comput. Sci. 2006).
We define strong λ-extendibility as a variant of the notion of λ-extendible properties of graphs (Poljak and Turzík, Discrete Mathematics, 1986). We show that the parameterized APT(Π) problem — given a connected graph G on n vertices and m edges and an integer parameter k, does there exist a spanning subgraph H of G such that H∈ΠH∈Π and H has at least λm+1−λ2(n−1)+k edges — is fixed-parameter tractable (FPT) for all 0<λ<10<λ<1, for all strongly λ-extendible graph properties Π for which the APT(Π ) problem is FPT on graphs which are O(k)O(k) vertices away from being a graph in which each block is a clique. Our results hold for properties of oriented graphs and graphs with edge labels, generalize the recent result of Crowston et al. (ICALP 2012) on Max-Cut parameterized above the Edwards–Erdős bound, and yield FPT algorithms for several graph problems parameterized above lower bounds.
Journal: Journal of Computer and System Sciences - Volume 80, Issue 7, November 2014, Pages 1384–1403