# FPT inapproximability of directed cut and connectivity problems

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

## Standard

**FPT inapproximability of directed cut and connectivity problems.** / Chitnis, Rajesh; Feldmann, Andreas Emil.

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

## Harvard

*14th International Symposium on Parameterized and Exact Computation, (IPEC 2019).*, 8, Leibniz International Proceedings in Informatics, LIPIcs, vol. 148, Schloss Dagstuhl, 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, Munich, Germany, 11/09/19. https://doi.org/10.4230/LIPIcs.IPEC.2019.8

## APA

*14th International Symposium on Parameterized and Exact Computation, (IPEC 2019)*[8] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 148). Schloss Dagstuhl. https://doi.org/10.4230/LIPIcs.IPEC.2019.8

## Vancouver

## Author

## Bibtex

}

## RIS

TY - GEN

T1 - FPT inapproximability of directed cut and connectivity problems

AU - Chitnis, Rajesh

AU - Feldmann, Andreas Emil

PY - 2019/12/1

Y1 - 2019/12/1

N2 - 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 2O(p2) · nO(1) time (i.e., a 2-approximation if k = 4), Under Gap-ETH, Directed Multicut does not admit an (5958 −ε)-approximation in f(p)·nO(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 k1/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 DSNPlanar 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 DSNPlanar: DSNPlanar 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]. DSNPlanar is W[1]-hard parameterized by k + p. Moreover, under ETH, there is no (1 + ε)- approximation for DSNPlanar in f(k, p, ε) · no(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 SCSSPlanar 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 SCSSPlanar: SCSSPlanar is W[1]-hard parameterized by k + p. Moreover, under ETH, there is no (1 + ε)- approximation for SCSSPlanar in f(k, p, ε) · no(√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].

AB - 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 2O(p2) · nO(1) time (i.e., a 2-approximation if k = 4), Under Gap-ETH, Directed Multicut does not admit an (5958 −ε)-approximation in f(p)·nO(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 k1/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 DSNPlanar 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 DSNPlanar: DSNPlanar 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]. DSNPlanar is W[1]-hard parameterized by k + p. Moreover, under ETH, there is no (1 + ε)- approximation for DSNPlanar in f(k, p, ε) · no(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 SCSSPlanar 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 SCSSPlanar: SCSSPlanar is W[1]-hard parameterized by k + p. Moreover, under ETH, there is no (1 + ε)- approximation for SCSSPlanar in f(k, p, ε) · no(√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].

KW - Connectivity

KW - Cuts

KW - Directed graphs

KW - FPT inapproximability

KW - Steiner problems

UR - http://www.scopus.com/inward/record.url?scp=85077440437&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.IPEC.2019.8

DO - 10.4230/LIPIcs.IPEC.2019.8

M3 - Conference contribution

AN - SCOPUS:85077440437

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 14th International Symposium on Parameterized and Exact Computation, (IPEC 2019)

A2 - Jansen, Bart M. P.

A2 - Telle, Jan Arne

PB - Schloss Dagstuhl

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

Y2 - 11 September 2019 through 13 September 2019

ER -