Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSimultaneous Feedback Edge Set: A Parameterized Perspective
58
0
0.0
(
0
)
Added by
Fahad Panolan
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper we consider Simultaneous Feedback Edge Set (Sim-FES) problem. In this problem, the input is an $n$-vertex graph $G$, an integer $k$ and a coloring function ${sf col}: E(G) rightarrow 2^{[alpha]}$ and the objective is to check whether there is an edge subset $S$ of cardinality at most $k$ in $G$ such that for all $i in [alpha]$, $G_i - S$ is acyclic. Here, $G_i=(V(G), {ein E(G) mid i in {sf col}(e)})$ and $[alpha]={1,ldots,alpha}$. When $alpha =1$, the problem is polynomial time solvable. We show that for $alpha =3$ Sim-FES is NP-hard by giving a reduction from Vertex Cover on cubic graphs. The same reduction shows that the problem does not admit an algorithm of running time $O(2^{o(k)}n^{O(1)})$ unless ETH fails. This hardness result is complimented by an FPT algorithm for Sim-FES running in time $O(2^{omega kalpha+alpha log k} n^{O(1)})$, where $omega$ is the exponent in the running time of matrix multiplication. The same algorithm gives a polynomial time algorithm for the case when $alpha =2$. We also give a kernel for Sim-FES with $(kalpha)^{O(alpha)}$ vertices. Finally, we consider the problem Maximum Simultaneous Acyclic Subgraph. Here, the input is a graph $G$, an integer $q$ and, a coloring function ${sf col}: E(G) rightarrow 2^{[alpha]}$. The question is whether there is a edge subset $F$ of cardinality at least $q$ in $G$ such that for all $iin [alpha]$, $G[F_i]$ is acyclic. Here, $F_i={e in F mid i in textsf{col}(e)}$. We give an FPT algorithm for running in time $O(2^{omega q alpha}n^{O(1)})$.
rate research
Read More
In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph $D$ on $n$ vertices and $m$ edges, and an integer $k$. The objective is to determine whether there exists a set of at most $k$ vertices intersecting every directed cycle of $D$. Whether or not DFVS admits a fixed parameter tractable (FPT) algorithm was considered the most important open problem in parameterized complexity until Chen, Liu, Lu, OSullivan and Razgon [JACM 2008] answered the question in the affirmative. They gave an algorithm for the problem with running time $O(k!4^kk^4nm)$. Since then, no faster algorithm for the problem has been found. In this paper, we give an algorithm for DFVS with running time $O(k!4^kk^5(n+m))$. Our algorithm is the first algorithm for DFVS with linear dependence on input size. Furthermore, the asymptotic dependence of the running time of our algorithm on the parameter $k$ matches up to a factor $k$ the algorithm of Chen, Liu, Lu, OSullivan and Razgon. On the way to designing our algorithm for DFVS, we give a general methodology to shave off a factor of $n$ from iterative-compression based algorithms for a few other well-studied covering problems in parameterized complexity. We demonstrate the applicability of this technique by speeding up by a factor of $n$, the current best FPT algorithms for Multicut [STOC 2011, SICOMP 2014] and Directed Subset Feedback Vertex Set [ICALP 2012, TALG 2014].
}We study (vertex-disjoint) $P_2$-packings in graphs under a parameterized perspective. Starting from a maximal $P_2$-packing $p$ of size $j$ we use extremal arguments for determining how many vertices of $p$ appear in some $P_2$-packing of size $(j+1)$. We basically can reuse $2.5j$ vertices. We also present a kernelization algorithm that gives a kernel of size bounded by $7k$. With these two results we build an algorithm which constructs a $P_2$-packing of size $k$ in time $Oh^*(2.482^{3k})$.
The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time $2^{O(tw)}n^{O(1)}$, for Feedback Vertex Set and connect
It has long been known that Feedback Vertex Set can be solved in time $2^{mathcal{O}(wlog w)}n^{mathcal{O}(1)}$ on $n$-vertex graphs of treewidth $w$, but it was only recently that this running time was improved to $2^{mathcal{O}(w)}n^{mathcal{O}(1)}$, that is, to single-exponential parameterized by treewidth. We investigate which generalizations of Feedback Vertex Set can be solved in a similar running time. Formally, for a class $mathcal{P}$ of graphs, the Bounded $mathcal{P}$-Block Vertex Deletion problem asks, given a graph~$G$ on $n$ vertices and positive integers~$k$ and~$d$, whether $G$ contains a set~$S$ of at most $k$ vertices such that each block of $G-S$ has at most $d$ vertices and is in $mathcal{P}$. Assuming that $mathcal{P}$ is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of $d$: if $mathcal{P}$ consists only of chordal graphs, then the problem can be solved in time $2^{mathcal{O}(wd^2)} n^{mathcal{O}(1)}$, and if $mathcal{P}$ contains a graph with an induced cycle of length $ellge 4$, then the problem is not solvable in time $2^{o(wlog w)} n^{mathcal{O}(1)}$ even for fixed $d=ell$, unless the ETH fails. We also study a similar problem, called Bounded $mathcal{P}$-Component Vertex Deletion, where the target graphs have connected components of small size rather than blocks of small size, and we present analogous results. For this problem, we also show that if $d$ is part of the input and $mathcal{P}$ contains all chordal graphs, then it cannot be solved in time $f(w)n^{o(w)}$ for some function $f$, unless the ETH fails.
We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G=(V,E) and an integer k, decide whether there exists a subset F of V, of size at most k, such that G[V F] is a forest and G[F] is connected. We show that Connected Feedback Vertex Set can be solved in time $O(2^{O(k)}n^{O(1)})$ on general graphs and in time $O(2^{O(sqrt{k}log k)}n^{O(1)})$ on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses as subroutine, a parameterized algorithm for Group Steiner Tree, a well studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree of independent interest and believe that it will be useful for obtaining parameterized algorithms for other connectivity problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
