# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Cut Problems
#### 4.5.1 Multicut  
An instance of Undirected Multicut (resp. Directed Multicut) is an undirected (resp. directed) graph \(G=(V,E)\) with \(k\) pairs of vertices \((s_{1},t_{1}),\ldots,(s_{k},t_{k})\). The goal is to remove the minimum number of edges such that there is no path from \(s_{i}\) to \(t_{i}\) for every \(i\in[k]\). Undirected Multiway cut (resp. Directed Multiway cut) is a special case of Undirected Multicut (resp. Directed Multiway cut) where \(k\) vertices are given as terminals and the goal is to make sure there is no path between any pair of terminals. They have been actively studied from both approximation and parameterized algorithms perspectives. We survey parameterized approximation algorithms for these problems with parameters \(k\) and the solution size Opt. **Undirected Multicut. ** Undirected Multicut admits an \(O(\log k)\)-approximation algorithm [223] in polynomial time, and is NP-hard to approximate within any constant factor assuming the Unique Games Conjecture [224]. Undirected Multiway cut admits an 1.2965-approximation algorithm [225] in polynomial time, and is NP-hard to approximate within a factor 1.20016 [226]. Undirected Multicut (and thus Undirected Multiway cut) admits an exact algorithm parametrized by Opt [219; 220]. With \(k\) as a parameter, we cannot hope for an exact algorithm or an approximation scheme, since even Undirected Multiway cut with 3 terminals is NP-hard to approximate within a factor \(12/11-\varepsilon\) for any \(\varepsilon>0\) under the Unique Games Conjecture. However, for Undirected Multicut with \(k\) pairs \((s_{1},t_{1}),\ldots,(s_{k},t_{k})\), one can reduce it to \(k^{O(k)}\) instances of Undirected Multiway cut with at most \(2k\) terminals, by guessing a partition of these \(s_{1},t_{1},\ldots,s_{k},t_{k}\) according to the connected components containing them in the optimal solution (e.g., \(s_{i}\) and \(t_{i}\) should be always in different groups), merging the vertices in the same group into one vertex, and solving Undirected Multiway cut with the merged vertices as terminals. This shows an 1.2965-approximation algorithm for Undirected Multicut that runs in time \(k^{O(k)}n^{O(1)}\). Some recent results improve or generalize this observation. For graphs with bounded genus \(g\), Cohen-Addad et al. [227] gave an EPAS running in time \(f(g,k,\varepsilon)\cdot n\log n\). Chekuri and Madan [228] considered the demand graph \(H\), which is the graph formed by \(k\) edges \((s_{1},t_{1}),\ldots,(s_{k},t_{k})\). When \(t\) is the smallest integer such that \(H\) does not contain \(t\) disjoint edges as an induced subgraph, they presented a 2-approximation algorithm that runs in time \(k^{O(t)}n^{O(1)}\). Directed MulticutGenerally, Directed Multicut is a much harder computational task than Undirected Multicut in terms of both approximation and parameterized algorithms. Directed Multicut admits a \(\min(k,\widetilde{O}(n^{11/23}))\)-approximation algorithm [229]. It is NP-hard to approximate within a factor \(k-\varepsilon\) for any \(\varepsilon>0\) for fixed \(k\)[230] under the Unique Games Conjecture, or \(2^{\Omega(\log^{1-\varepsilon}n)}\) for any \(\varepsilon>0\)[231] for general \(k\). Directed Multiway cut admits an 2-approximation algorithm [232], which is tight even when \(k=2\)[230]. Parameterizing by Opt, Directed Multicut is FPT for \(k=2\), but Directed Multicut is W[1]-hard even when \(k=4\)[46]. Directed Multiway cut on the other hand is in FPT [221]. Since it is hard to improve the trivial \(k\)-approximation algorithm even for fixed \(k\)[230], parameterizing by \(k\) does not yield a better approximation algorithm. Chitnis and Feldmann [233] gave a \(k/2\)-approximation algorithm that runs in time \(2^{O(\textsc{Opt}^{2})}n^{O(1)}\), and also proved that the problem under the same parameterization is still hard to approximate within a factor \(59/58\) with \(k=4\). **Open Question 14**. : _What is the best approximation ratio (as a function of \(k\)) achieved by a parameterized algorithm (with parameter Opt)?