Name
Abstract | ||
|---|---|---|
A knot in a directed graph $G$ is a strongly connected subgraph $Q$ of $G$ with at least two vertices, such that no vertex in $V(Q)$ is an in-neighbor of a vertex in $V(G)\setminus V(Q)$. Knots are important graph structures, because they characterize the existence of deadlocks in a classical distributed computation model, the so-called OR-model. Deadlock detection is correlated with the recognition of knot-free graphs as well as deadlock resolution is closely related to the {\sc Knot-Free Vertex Deletion (KFVD)} problem, which consists of determining whether an input graph $G$ has a subset $S \subseteq V(G)$ of size at most $k$ such that $G[V\setminus S]$ contains no knot. In this paper we focus on graph width measure parameterizations for {\sc KFVD}. First, we show that: (i) {\sc KFVD} parameterized by the size of the solution $k$ is W[1]-hard even when $p$, the length of a longest directed path of the input graph, as well as $\kappa$, its Kenny-width, are bounded by constants, and we remark that {\sc KFVD} is para-NP-hard even considering many directed width measures as parameters, but in FPT when parameterized by clique-width; (ii) {\sc KFVD} can be solved in time $2^{O(tw)}\times n$, but assuming ETH it cannot be solved in $2^{o(tw)}\times n^{O(1)}$, where $tw$ is the treewidth of the underlying undirected graph. Finally, since the size of a minimum directed feedback vertex set ($dfv$) is an upper bound for the size of a minimum knot-free vertex deletion set, we investigate parameterization by $dfv$ and we show that (iii) {\sc KFVD} can be solved in FPT-time parameterized by either $dfv+\kappa$ or $dfv+p$; and it admits a Turing kernel by the distance to a DAG having an Hamiltonian path. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.4230/LIPIcs.IPEC.2019.2 | IPEC |
Field | DocType | Citations |
Combinatorics,Vertex deletion,Knot (unit),Mathematics | Conference | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stéphane Bessy | 1 | 117 | 19.68 |
| Marin Bougeret | 2 | 113 | 13.35 |
| Alan Diêgo A. Carneiro | 3 | 1 | 0.69 |
| Fábio Protti | 4 | 357 | 46.14 |
| Uéverton S. Souza | 5 | 20 | 21.12 |