In the Rectangle Stabbing problem, input is a set R of axis-parallel rectangles and a set L of axis-parallel lines in the plane. The task is to find a minimum size set L^* ⊆ L such that for every rectangle R ∈ R there is a line 𝓁 ∈ L^* such that 𝓁 intersects R. Gaur et al. [Journal of Algorithms, 2002] gave a polynomial time 2-approximation algorithm, while Dom et al. [WALCOM 2009] and Giannopoulos et al. [EuroCG 2009] independently showed that, assuming FPT ≠ W[1], there is no algorithm with running time f(k)(|L||R|)^O(1) that determines whether there exists an optimal solution with at most k lines. We give the first parameterized approximation algorithm for the problem with a ratio better than 2. In particular we give an algorithm that given R, L, and an integer k runs in time k^O(k)(|L||R|)^O(1) and either correctly concludes that there does not exist a solution with at most k lines, or produces a solution with at most 7k/4 lines. We complement our algorithm by showing that unless FPT = W[1], the Rectangle Stabbing problem does not admit a (5/4-ε)-approximation algorithm running in f(k)(|L||R|)^O(1) time for any function f and ε > 0.

Treewidth is a useful tool in designing graph algorithms. Although many NP-hard graph problems can be solved in linear time when the input graphs have small treewidth, there are problems which remain hard on graphs of bounded treewidth. In this paper, we consider three vertex selection problems that are W[1]-hard when parameterized by the treewidth of the input graph, namely the capacitated vertex cover problem, the target set selection problem and the vector dominating set problem. We provide two new methods to obtain FPT approximation algorithms for these problems. For the capacitated vertex cover problem and the vector dominating set problem, we obtain $(1+o(1))$-approximation FPT algorithms. For the target set selection problem, we give an FPT algorithm providing a tradeoff between its running time and the approximation ratio.

We show that the CNF satisfiability problem can be solved O^*(1.2226^m) time, where m is the number of clauses in the formula, improving the known upper bounds O^*(1.234^m) given by Yamamoto 15 years ago and O^*(1.239^m) given by Hirsch 22 years ago. By using an amortized technique and careful case analysis, we successfully avoid the bottlenecks in previous algorithms and get the improvement.