ﻻ يوجد ملخص باللغة العربية
A skew-symmetric graph $(D=(V,A),sigma)$ is a directed graph $D$ with an involution $sigma$ on the set of vertices and arcs. In this paper, we introduce a separation problem, $d$-Skew-Symmetric Multicut, where we are given a skew-symmetric graph $D$, a family of $cal T$ of $d$-sized subsets of vertices and an integer $k$. The objective is to decide if there is a set $Xsubseteq A$ of $k$ arcs such that every set $J$ in the family has a vertex $v$ such that $v$ and $sigma(v)$ are in different connected components of $D=(V,Asetminus (Xcup sigma(X))$. In this paper, we give an algorithm for this problem which runs in time $O((4d)^{k}(m+n+ell))$, where $m$ is the number of arcs in the graph, $n$ the number of vertices and $ell$ the length of the family given in the input. Using our algorithm, we show that Almost 2-SAT has an algorithm with running time $O(4^kk^4ell)$ and we obtain algorithms for {sc Odd Cycle Transversal} and {sc Edge Bipartization} which run in time $O(4^kk^4(m+n))$ and $O(4^kk^5(m+n))$ respectively. This resolves an open problem posed by Reed, Smith and Vetta [Operations Research Letters, 2003] and improves upon the earlier almost linear time algorithm of Kawarabayashi and Reed [SODA, 2010]. We also show that Deletion q-Horn Backdoor Set Detection is a special case of 3-Skew-Symmetric Multicut, giving us an algorithm for Deletion q-Horn Backdoor Set Detection which runs in time $O(12^kk^5ell)$. This gives the first fixed-parameter tractable algorithm for this problem answering a question posed in a paper by a superset of the authors [STACS, 2013]. Using this result, we get an algorithm for Satisfiability which runs in time $O(12^kk^5ell)$ where $k$ is the size of the smallest q-Horn deletion backdoor set, with $ell$ being the length of the input formula.
In the Subset Sum problem we are given a set of $n$ positive integers $X$ and a target $t$ and are asked whether some subset of $X$ sums to $t$. Natural parameters for this problem that have been studied in the literature are $n$ and $t$ as well as t
We study the algorithmic properties of the graph class Chordal-ke, that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. We discover that a number of fundamental
Given a graph $G=(V,E)$, two vertices $s,tin V$, and two integers $k,ell$, the Short Secluded Path problem is to find a simple $s$-$t$-path with at most $k$ vertices and $ell$ neighbors. We study the parameterized complexity of the problem with respe
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)}
In this paper we show how to recover a spectral approximations to broad classes of structured matrices using only a polylogarithmic number of adaptive linear measurements to either the matrix or its inverse. Leveraging this result we obtain faster al