text: Every triangle-free planar graph on n vertices has an independent set of size at least (n+1) 3, and this lower bound is tight. We give an algorithm that, given a triangle-free planar graph G on n vertices and an integer k>=0, decides whether G has an independent set of size at least (n+k) 3, in time 2^ O(sqrt k ) n. Thus, the problem is fixed-parameter tractable when parameterized by k. Furthermore, as a corollary of the result used to prove the correctness of the algorithm, we show that there exists epsilon>0 such that every planar graph of girth at least five on n vertices has an independent set of size at least n (3-epsilon).
  @cite_30: 
  @cite_35: We study ordinal embedding relaxations in the realm of parameterized complexity. We prove the existence of a quadratic kernel for the Betweenness problem parameterized above its tight lower bound, which is stated as follows. For a set V of variables and set C of constraints ''v"i is between v"j and v"k'', decide whether there is a bijection from V to the set 1,...,|V| satisfying at least |C| 3+@k of the constraints in C. Our result solves an open problem attributed to Benny Chor in Niedermeier's monograph ''Invitation to Fixed-Parameter Algorithms''. The betweenness problem is of interest in molecular biology. An approach developed in this paper can be used to determine parameterized complexity of a number of other optimization problems on permutations parameterized above or below tight bounds.
  @cite_9: We study the boundary of tractability for the Max-Cut problem in graphs. Our main result shows that Max-Cut above the Edwards-Erd o s bound is fixed-parameter tractable: we give an algorithm that for any connected graph with n vertices and m edges finds a cut of size m 2 + (n-1) 4 + k in time 2^O(k)n^4, or decides that no such cut exists. This answers a long-standing open question from parameterized complexity that has been posed several times over the past 15 years. Our algorithm is asymptotically optimal, under the Exponential Time Hypothesis, and is strengthened by a polynomial-time computable kernel of polynomial size.
  @cite_24: A ternary Permutation-CSP is specified by a subset @P of the symmetric group S"3. An instance of such a problem consists of a set of variables V and a multiset of constraints, which are ordered triples of distinct variables of V. The objective is to find a linear ordering @a of V that maximizes the number of triples whose rearrangement (under @a) follows a permutation in @P. We prove that every ternary Permutation-CSP parameterized above average has a kernel with a quadratic number of variables.
  @cite_2: We consider new parameterizations of NP-optimization problems that have nontrivial lower and or upper bounds on their optimum solution size. The natural parameter, we argue, is the quantity above the lower bound or below the upper bound. We show that for every problem in MAX SNP, the optimum value is bounded below by an unbounded function of the input-size, and that the above-guarantee parameterization with respect to this lower bound is fixed-parameter tractable. We also observe that approximation algorithms give nontrivial lower or upper bounds on the solution size and that the above or below guarantee question with respect to these bounds is fixed-parameter tractable for a subclass of NP-optimization problems. We then introduce the notion of 'tight' lower and upper bounds and exhibit a number of problems for which the above-guarantee and below-guarantee parameterizations with respect to a tight bound is fixed-parameter tractable or W-hard. We show that if we parameterize ''sufficiently'' above or below the tight bounds, then these parameterized versions are not fixed-parameter tractable unless P=NP, for a subclass of NP-optimization problems. We also list several directions to explore in this paradigm.
  @cite_5: A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differ by at most one, and the size of the bisection is the number of edges which go across the two parts. Every graph with m edges has a bisection of size at least ⌈m 2 ⌉, and this bound is sharp for infinitely many graphs. Therefore, Gutin and Yeo considered the parameterized complexity of deciding whether an input graph with m edges has a bisection of size at least ⌈m 2 ⌉+k, where k is the parameter. They showed fixed-parameter tractability of this problem, and gave a kernel with O(k2) vertices. Here, we improve the kernel size to O(k) vertices. Under the Exponential Time Hypothesis, this result is best possible up to constant factors.
  @cite_13: We introduce a concept of parameterizing a problem above the optimum solution of its natural linear programming relaxation and prove that the node multiway cut problem is fixed-parameter tractable (FPT) in this setting. As a consequence we prove that node multiway cut is FPT, when parameterized above the maximum separating cut, resolving an open problem of Razgon. Our results imply O*(4k) algorithms for vertex cover above maximum matching and almost 2-SAT as well as an O*(2k) algorithm for node multiway cut with a standard parameterization by the solution size, improving previous bounds for these problems.
  @cite_17: We present an exact algorithm that decides, for every fixed r ≥ 2 in time O(m) + 2O(k2) whether a given set of m clauses of size r admits a truth assignment that satisfies at least ((2r - 1)m + k) 2r clauses. Thus Max-r-Sat is fixed-parameter tractable when parameterized by the number of satisfied clauses above the tight lower bound (1--2-r)m. This solves an open problem of Mahajan, Raman and Sikdar (J. Comput. System Sci., 75, 2009). Our algorithm is based on a polynomial-time data reduction procedure that reduces a problem instance to an equivalent algebraically represented problem with O(k2) variables. This is done by representing the instance as an appropriate polynomial, and by applying a probabilistic argument combined with some simple tools from Harmonic analysis to show that if the polynomial cannot be reduced to one of size O(k2), then there is a truth assignment satisfying the required number of clauses. Combining another probabilistic argument with tools from graph matching theory and signed graphs, we show that if an instance of Max-2-Sat with m clauses has at least 3k variables after application of certain polynomial time reduction rules to it, then there is a truth assignment that satisfies at least (3m + k) 4 clauses. We also outline how the fixed-parameter tractability result on Max-r-Sat can be extended to a family of Boolean Constraint Satisfaction Problems.
summary: From the algorithmic side, the studying the complexity of maximization problems parameterized above polynomial-time computable lower bounds is an active area of research. Since the influental survey by @cite_2 , research in this area has led to development of many new algorithmic techniques for fixed-parameter algorithms: algebraic methods @cite_17 @cite_30 , probabilistic methods @cite_35 @cite_24 , combinatorial methods @cite_9 @cite_5 , and methods based on linear programming @cite_13 .