# FPT inapproximability of directed cut and connectivity problems

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Authors

## Colleges, School and Institutes

## External organisations

- Charles University, Prague

## Abstract

Cut problems and connectivity problems on digraphs are two well-studied classes of problems from the viewpoint of parameterized complexity. After a series of papers over the last decade, we now have (almost) tight bounds for the running time of several standard variants of these problems parameterized by two parameters: the number k of terminals and the size p of the solution. When there is evidence of FPT intractability, then the next natural alternative is to consider FPT approximations. In this paper, we show two types of results for directed cut and connectivity problems, building on existing results from the literature: first is to circumvent the hardness results for these problems by designing FPT approximation algorithms, or alternatively strengthen the existing hardness results by creating “gap-instances” under stronger hypotheses such as the (Gap-)Exponential Time Hypothesis (ETH). Formally, we show the following results: Cutting paths between a set of terminal pairs, i.e., Directed Multicut: Pilipczuk and Wahlstrom [TOCT'18] showed that Directed Multicut is W[1]-hard when parameterized by p if k = 4. We complement this by showing the following two results: Directed Multicut has a k/2-approximation in 2^{O}(^{p}^{2)} · n^{O}^{(1)} time (i.e., a 2-approximation if k = 4), Under Gap-ETH, Directed Multicut does not admit an (^{59}_{58} −ε)-approximation in f(p)·n^{O}(1) time, for any computable function f, even if k = 4. Connecting a set of terminal pairs, i.e., Directed Steiner Network (DSN): The DSN problem on general graphs is known to be W[1]-hard parameterized by p + k due to Guo et al. [SIDMA'11]. Dinur and Manurangsi [ITCS'18] further showed that there is no FPT k^{1}/4−o^{(1)}-approximation algorithm parameterized by k, under Gap-ETH. Chitnis et al. [SODA'14] considered the restriction to special graph classes, but unfortunately this does not lead to FPT algorithms either: DSN on planar graphs is W[1]-hard parameterized by k. In this paper we consider the DSN_{Planar} problem which is an intermediate version: the graph is general, but we want to find a solution whose cost is at most that of an optimal planar solution (if one exists). We show the following lower bounds for DSN_{Planar}: DSN_{Planar} has no (2 − ε)-approximation in FPT time parameterized by k, under Gap-ETH. This answers in the negative a question of Chitnis et al. [ESA'18]. DSN_{Planar} is W[1]-hard parameterized by k + p. Moreover, under ETH, there is no (1 + ε)- approximation for DSN_{Planar} in f(k, p, ε) · n^{o}(k+√p+1/ε^{)} time for any computable function f. Pairwise connecting a set of terminals, i.e., Strongly Connected Steiner Subgraph (SCSS): Guo et al. [SIDMA'11] showed that SCSS is W[1]-hard parameterized by p + k, while Chitnis et al. [SODA'14] showed that SCSS remains W[1]-hard parameterized by p, even if the input graph is planar. In this paper we consider the SCSS_{Planar} problem which is an intermediate version: the graph is general, but we want to find a solution whose cost is at most that of an optimal planar solution (if one exists). We show the following lower bounds for SCSS_{Planar}: SCSS_{Planar} is W[1]-hard parameterized by k + p. Moreover, under ETH, there is no (1 + ε)- approximation for SCSS_{Planar} in f(k, p, ε) · n^{o}(√k+p^{+ 1ε )} time for any computable function f. Previously, the only known FPT approximation results for SCSS applied to general graphs parameterized by k: a 2-approximation by Chitnis et al. [IPEC'13], and a matching (2 − ε)-hardness under Gap-ETH by Chitnis et al. [ESA'18].

## Details

Original language | English |
---|---|

Title of host publication | 14th International Symposium on Parameterized and Exact Computation, (IPEC 2019) |

Editors | Bart M. P. Jansen, Jan Arne Telle |

Publication status | Published - 1 Dec 2019 |

Event | 14th International Symposium on Parameterized and Exact Computation, IPEC 2019 - Munich, Germany Duration: 11 Sep 2019 → 13 Sep 2019 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 148 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 14th International Symposium on Parameterized and Exact Computation, IPEC 2019 |
---|---|

Country | Germany |

City | Munich |

Period | 11/09/19 → 13/09/19 |

## Keywords

- Connectivity, Cuts, Directed graphs, FPT inapproximability, Steiner problems