|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Component Order Connectivity in Directed Graphs | | J. Bang-Jensen
; E. Eiben
; G. Gutin
; M. Wahlstrom
; A. Yeo
; | | Date: |
14 Jul 2020 | | Abstract: | A directed graph $D$ is semicomplete if for every pair $x,y$ of vertices of
$D,$ there is at least one arc between $x$ and $y.$ viol{Thus, a tournament is
a semicomplete digraph.} In the Directed Component Order Connectivity (DCOC)
problem, given a digraph $D=(V,A)$ and a pair of natural numbers $k$ and
$ell$, we are to decide whether there is a subset $X$ of $V$ of size $k$ such
that the largest strong connectivity component in $D-X$ has at most $ell$
vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem
for $ell=1.$ We study parametered complexity of DCOC for general and
semicomplete digraphs with the following parameters: $k, ell,ell+k$ and
$n-ell$. In particular, we prove that DCOC with parameter $k$ on semicomplete
digraphs can be solved in time $O^*(2^{16k})$ but not in time $O^*(2^{o(k)})$
unless the Exponential Time Hypothesis (ETH) fails. gutin{The upper bound
$O^*(2^{16k})$ implies the upper bound $O^*(2^{16(n-ell)})$ for the parameter
$n-ell.$ We complement the latter by showing that there is no algorithm of
time complexity $O^*(2^{o({n-ell})})$ unless ETH fails.} Finally, we improve
viol{(in dependency on $ell$)} the upper bound of G{"{o}}ke, Marx and Mnich
(2019) for the time complexity of DCOC with parameter $ell+k$ on general
digraphs from $O^*(2^{O(kelllog (kell))})$ to $O^*(2^{O(klog (kell))}).$
Note that Drange, Dregi and van ’t Hof (2016) proved that even for the
undirected version of DCOC on split graphs there is no algorithm of running
time $O^*(2^{o(klog ell)})$ unless ETH fails and it is a long-standing
problem to decide whether Directed Feedback Vertex Set admits an algorithm of
time complexity $O^*(2^{o(klog k)}).$ | | Source: | arXiv, 2007.6896 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER