Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userParameterized Complexity and Approximability of Directed Odd Cycle Transversal
289
0
0.0
(
0
)
Added by
Ramanujan M. S.
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A directed odd cycle transversal of a directed graph (digraph) $D$ is a vertex set $S$ that intersects every odd directed cycle of $D$. In the Directed Odd Cycle Transversal (DOCT) problem, the input consists of a digraph $D$ and an integer $k$. The objective is to determine whether there exists a directed odd cycle transversal of $D$ of size at most $k$. In this paper, we settle the parameterized complexity of DOCT when parameterized by the solution size $k$ by showing that DOCT does not admit an algorithm with running time $f(k)n^{O(1)}$ unless FPT = W[1]. On the positive side, we give a factor $2$ fixed parameter tractable (FPT) approximation algorithm for the problem. More precisely, our algorithm takes as input $D$ and $k$, runs in time $2^{O(k^2)}n^{O(1)}$, and either concludes that $D$ does not have a directed odd cycle transversal of size at most $k$, or produces a solution of size at most $2k$. Finally, we provide evidence that there exists $epsilon > 0$ such that DOCT does not admit a factor $(1+epsilon)$ FPT-approximation algorithm.
rate research
Read More
We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on $H$-free graphs, that is, graphs that do not contain some fixed graph $H$ as an induced subgraph. In particular, we prove that both problems are polynomial-time solvable for $sP_3$-free graphs for every integer $sgeq 1$. Our results show that both problems exhibit the same behaviour on $H$-free graphs (subject to some open cases). This is in part explained by a new general algorithm we design for finding in a graph $G$ a largest induced subgraph whose blocks belong to some finite class ${cal C}$ of graphs. We also compare our results with the state-of-the-art results for the Odd Cycle Transversal problem, which is known to behave differently on $H$-free graphs.
Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the parameterized complexity of the following problems parameterized by $k$: (1) Given a graph $G$, a clique modulator $D$ (a clique modulator is a set of vertices, whose removal results in a clique) of size $k$ for $G$, and a list $L(v)$ of colors for every $vin V(G)$, decide whether $G$ has a proper list coloring; (2) Given a graph $G$, a clique modulator $D$ of size $k$ for $G$, and a pre-coloring $lambda_P: X rightarrow Q$ for $X subseteq V(G),$ decide whether $lambda_P$ can be extended to a proper coloring of $G$ using only colors from $Q.$ For Problem 1 we design an $O^*(2^k)$-time randomized algorithm and for Problem 2 we obtain a kernel with at most $3k$ vertices. Banik et al. (IWOCA 2019) proved the the following problem is fixed-parameter tractable and asked whether it admits a polynomial kernel: Given a graph $G$, an integer $k$, and a list $L(v)$ of exactly $n-k$ colors for every $v in V(G),$ decide whether there is a proper list coloring for $G.$ We obtain a kernel with $O(k^2)$ vertices and colors and a compression to a variation of the problem with $O(k)$ vertices and $O(k^2)$ colors.
The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization that has been recently proposed is the $k$-anonymity. This approach requires that the rows of a table are partitioned in clusters of size at least $k$ and that all the rows in a cluster become the same tuple, after the suppression of some entries. The natural optimization problem, where the goal is to minimize the number of suppressed entries, is known to be APX-hard even when the records values are over a binary alphabet and $k=3$, and when the records have length at most 8 and $k=4$ . In this paper we study how the complexity of the problem is influenced by different parameters. In this paper we follow this direction of research, first showing that the problem is W[1]-hard when parameterized by the size of the solution (and the value $k$). Then we exhibit a fixed parameter algorithm, when the problem is parameterized by the size of the alphabet and the number of columns. Finally, we investigate the computational (and approximation) complexity of the $k$-anonymity problem, when restricting the instance to records having length bounded by 3 and $k=3$. We show that such a restriction is APX-hard.
}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 elimination distance to some target graph property P is a general graph modification parameter introduced by Bulian and Dawar. We initiate the study of elimination distances to graph properties expressible in first-order logic. We delimit the problems fixed-parameter tractability by identifying sufficient and necessary conditions on the structure of prefixes of first-order logic formulas. Our main result is the following meta-theorem: for every graph property P expressible by a first order-logic formula phiin Sigma_3, that is, of the form phi=exists x_1exists x_2cdots exists x_r forall y_1forall y_2cdots forall y_s exists z_1exists z_2cdots exists z_t psi, where psi is a quantifier-free first-order formula, checking whether the elimination distance of a graph to P does not exceed k, is fixed-parameter tractable parameterized by k. Properties of graphs expressible by formulas from Sigma_3 include being of bounded degree, excluding a forbidden subgraph, or containing a bounded dominating set. We complement this theorem by showing that such a general statement does not hold for formulas with even slightly more expressive prefix structure: there are formulas phiin Pi_3, for which computing elimination distance is W[2]-hard.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
