Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929488326033408 |
|---|---|
| author | Włodarczyk, Michał |
| author_facet | Włodarczyk, Michał |
| contents | In the Disjoint Paths problem, one is given a graph with a set of $k$ vertex pairs $(s_i,t_i)$ and the task is to connect each $s_i$ to $t_i$ with a path, so that the $k$ paths are pairwise disjoint. In the optimization variant, Max Disjoint Paths, the goal is to maximize the number of vertex pairs to be connected. We study this problem on acyclic directed graphs, where Disjoint Paths is known to be W[1]-hard when parameterized by $k$. We show that in this setting Max Disjoint Paths is W[1]-hard to $c$-approximate for any constant $c$. To the best of our knowledge, this is the first non-trivial result regarding the parameterized approximation for Max Disjoint Paths with respect to the natural parameter $k$. Our proof is based on an elementary self-reduction that is guided by a certain combinatorial object constructed by the probabilistic method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_03596 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard Włodarczyk, Michał Data Structures and Algorithms In the Disjoint Paths problem, one is given a graph with a set of $k$ vertex pairs $(s_i,t_i)$ and the task is to connect each $s_i$ to $t_i$ with a path, so that the $k$ paths are pairwise disjoint. In the optimization variant, Max Disjoint Paths, the goal is to maximize the number of vertex pairs to be connected. We study this problem on acyclic directed graphs, where Disjoint Paths is known to be W[1]-hard when parameterized by $k$. We show that in this setting Max Disjoint Paths is W[1]-hard to $c$-approximate for any constant $c$. To the best of our knowledge, this is the first non-trivial result regarding the parameterized approximation for Max Disjoint Paths with respect to the natural parameter $k$. Our proof is based on an elementary self-reduction that is guided by a certain combinatorial object constructed by the probabilistic method. |
| title | Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.03596 |