The Experts below are selected from a list of 13506 Experts worldwide ranked by ideXlab platform
Saket Saurabh - One of the best experts on this subject based on the ideXlab platform.
-
linear time parameterized algorithms via Skew Symmetric multicuts
ACM Transactions on Algorithms, 2017Co-Authors: M S Ramanujan, Saket SaurabhAbstract:A Skew-Symmetric graph (D=(V,A),σ) is a directed graph D with an involution σ on the set of vertices and arcs. Flows on Skew-Symmetric graphs have been used to generalize maximum flow and maximum matching problems on graphs, initially by Tutte and later by Goldberg and Karzanov. In this article, we introduce a separation problem, d-Skew-Symmetric Multicut, where we are given a Skew-Symmetric graph D, a family τ of d-size subsets of vertices, and an integer k. The objective is to decide whether there is a set X s A of k arcs such that every set J in the family has a vertex u such that u and σ(u) are in different strongly connected components of D′=(V,A b (X ∪ σ(X)). In this work, we give an algorithm for d-Skew-Symmetric Multicut that runs in time O((4d)k(m+n+e)), where m is the number of arcs in the graph, n is the number of vertices, and e is the length of the family given in the input.This problem, apart from being independently interesting, also captures the main combinatorial difficulty of numerous classical problems. Our algorithm for d-Skew-Symmetric Multicut paves the way for the first linear-time parameterized algorithms for several problems. We demonstrate its utility by obtaining the following linear-time parameterized algorithms:— We show that Almost 2-SAT is a special case of 1-Skew-Symmetric Multicut, resulting in an algorithm for Almost 2-SAT that runs in time O(4kk4e), where k is the size of the solution and e is the length of the input formula. Then, using linear-time parameter-preserving reductions to Almost 2-SAT, we obtain algorithms for Odd Cycle Transversal and Edge Bipartization that run in time O(4kk4(m+n)) and O(4kk5(m+n)), respectively, where k is the size of the solution, and m and n are the number of edges and vertices respectively. This resolves an open problem posed by Reed et al. and improves on the earlier almost-linear-time algorithm of Kawarabayashi and Reed.— We 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 that runs in time O(12kk5e), where k is the size of the solution and e is the length of the input formula. This gives the first fixed-parameter tractable algorithm for this problem answering a question posed in a work by Narayanaswamy et al. Using this result, we get an algorithm for Satisfiability that runs in time O(12kk5e), where k is the size of the smallest q-Horn deletion backdoor set, with e being the length of the input formula.
-
linear time parameterized algorithms via Skew Symmetric multicuts
Symposium on Discrete Algorithms, 2014Co-Authors: M S Ramanujan, Saket SaurabhAbstract:A Skew-Symmetric graph (D = (V, A), σ) is a directed graph D with an involution σ on the set of vertices and arcs. Flows on Skew-Symmetric graphs have been used to generalize maximum flow and maximum matching problems on graphs, initially by Tutte [1967], and later by Goldberg and Karzanov [1994, 1995]. In this paper, we introduce a separation problem, d-Skew-Symmetric Multicut, where we are given a Skew-Symmetric graph D, a family of T of d-sized subsets of vertices and an integer k. The objective is to decide if there is a set X ⊆ A of k arcs such that every set J in the family has a vertex v such that v and σ(v) are in different strongly connected components of D' = (V, A \ (X ∪ σ(X)). In this paper, we give an algorithm for d-Skew-Symmetric Multicut which runs in time O((4d)k(m+n+e)), where m is the number of arcs in the graph, n the number of vertices and e the length of the family given in the input.This problem, apart from being independently interesting, also abstracts out and captures the main combinatorial obstacles towards solving numerous classical problems. Our algorithm for d-Skew-Symmetric Multicut paves the way for the first linear time parameterized algorithms for several problems. We demonstrate its utility by obtaining the following linear time parameterized algorithms.• We show that Almost 2-SAT is a special case of 1-Skew-Symmetric Multicut, resulting in an algorithm for Almost 2-SAT which runs in time O(4kk4e) where k is the size of the solution and e is the length of the input formula. Then, using linear time parameter preserving reductions to Almost 2-SAT, we obtain algorithms for Odd Cycle Transversal and Edge Bipartization which run in time O(4kk4(m+n)) and O(4kk5(m+n)) respectively where k is size of the solution, m and n are the number of edges and vertices 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 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(12kk5e) where k is the size of the solution and e is the length of the input formula. 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(12kk5e) where k is the size of the smallest q-Horn deletion backdoor set, with e being the length of the input formula.
Daizhan Cheng - One of the best experts on this subject based on the ideXlab platform.
-
On Skew-Symmetric games
Journal of the Franklin Institute, 2018Co-Authors: Yaqi Hao, Daizhan ChengAbstract:Abstract By resorting to the vector space structure of finite games, Skew-Symmetric games (SSGs) are proposed and investigated as a natural subspace of finite games. First of all, for two player games, it is shown that the Skew-Symmetric games form an orthogonal complement of the Symmetric games. Then for a general SSG its linear representation is given, which can be used to verify whether a finite game is Skew-Symmetric. Furthermore, some properties of SSGs are also obtained in the light of its vector subspace structure. Finally, a symmetry-based decomposition of finite games is proposed, which consists of three mutually orthogonal subspaces: Symmetric subspace, Skew-Symmetric subspace and aSymmetric subspace. An illustrative example is presented to demonstrate this decomposition.
-
From Symmetric to Skew-Symmetric games
2017 Chinese Automation Congress (CAC), 2017Co-Authors: Yaqi Hao, Daizhan ChengAbstract:As a natural dual object of Symmetric game (SG), the Skew-Symmetric game (SSG) is proposed and investigated in this paper. First of all, for two player games, it is shown that both Symmetric and Skew-Symmetric games are subspaces of finite games. Moreover, using the Euclidean space structure of finite games, it is proved that the Skew-Symmetric games form an orthogonal complement of Symmetric games. Then the linear representation of SSG is presented, which can be used to verify whether a finite game is a SSG. Finally, some properties of SSGs are revealed.
M S Ramanujan - One of the best experts on this subject based on the ideXlab platform.
-
linear time parameterized algorithms via Skew Symmetric multicuts
ACM Transactions on Algorithms, 2017Co-Authors: M S Ramanujan, Saket SaurabhAbstract:A Skew-Symmetric graph (D=(V,A),σ) is a directed graph D with an involution σ on the set of vertices and arcs. Flows on Skew-Symmetric graphs have been used to generalize maximum flow and maximum matching problems on graphs, initially by Tutte and later by Goldberg and Karzanov. In this article, we introduce a separation problem, d-Skew-Symmetric Multicut, where we are given a Skew-Symmetric graph D, a family τ of d-size subsets of vertices, and an integer k. The objective is to decide whether there is a set X s A of k arcs such that every set J in the family has a vertex u such that u and σ(u) are in different strongly connected components of D′=(V,A b (X ∪ σ(X)). In this work, we give an algorithm for d-Skew-Symmetric Multicut that runs in time O((4d)k(m+n+e)), where m is the number of arcs in the graph, n is the number of vertices, and e is the length of the family given in the input.This problem, apart from being independently interesting, also captures the main combinatorial difficulty of numerous classical problems. Our algorithm for d-Skew-Symmetric Multicut paves the way for the first linear-time parameterized algorithms for several problems. We demonstrate its utility by obtaining the following linear-time parameterized algorithms:— We show that Almost 2-SAT is a special case of 1-Skew-Symmetric Multicut, resulting in an algorithm for Almost 2-SAT that runs in time O(4kk4e), where k is the size of the solution and e is the length of the input formula. Then, using linear-time parameter-preserving reductions to Almost 2-SAT, we obtain algorithms for Odd Cycle Transversal and Edge Bipartization that run in time O(4kk4(m+n)) and O(4kk5(m+n)), respectively, where k is the size of the solution, and m and n are the number of edges and vertices respectively. This resolves an open problem posed by Reed et al. and improves on the earlier almost-linear-time algorithm of Kawarabayashi and Reed.— We 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 that runs in time O(12kk5e), where k is the size of the solution and e is the length of the input formula. This gives the first fixed-parameter tractable algorithm for this problem answering a question posed in a work by Narayanaswamy et al. Using this result, we get an algorithm for Satisfiability that runs in time O(12kk5e), where k is the size of the smallest q-Horn deletion backdoor set, with e being the length of the input formula.
-
linear time parameterized algorithms via Skew Symmetric multicuts
Symposium on Discrete Algorithms, 2014Co-Authors: M S Ramanujan, Saket SaurabhAbstract:A Skew-Symmetric graph (D = (V, A), σ) is a directed graph D with an involution σ on the set of vertices and arcs. Flows on Skew-Symmetric graphs have been used to generalize maximum flow and maximum matching problems on graphs, initially by Tutte [1967], and later by Goldberg and Karzanov [1994, 1995]. In this paper, we introduce a separation problem, d-Skew-Symmetric Multicut, where we are given a Skew-Symmetric graph D, a family of T of d-sized subsets of vertices and an integer k. The objective is to decide if there is a set X ⊆ A of k arcs such that every set J in the family has a vertex v such that v and σ(v) are in different strongly connected components of D' = (V, A \ (X ∪ σ(X)). In this paper, we give an algorithm for d-Skew-Symmetric Multicut which runs in time O((4d)k(m+n+e)), where m is the number of arcs in the graph, n the number of vertices and e the length of the family given in the input.This problem, apart from being independently interesting, also abstracts out and captures the main combinatorial obstacles towards solving numerous classical problems. Our algorithm for d-Skew-Symmetric Multicut paves the way for the first linear time parameterized algorithms for several problems. We demonstrate its utility by obtaining the following linear time parameterized algorithms.• We show that Almost 2-SAT is a special case of 1-Skew-Symmetric Multicut, resulting in an algorithm for Almost 2-SAT which runs in time O(4kk4e) where k is the size of the solution and e is the length of the input formula. Then, using linear time parameter preserving reductions to Almost 2-SAT, we obtain algorithms for Odd Cycle Transversal and Edge Bipartization which run in time O(4kk4(m+n)) and O(4kk5(m+n)) respectively where k is size of the solution, m and n are the number of edges and vertices 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 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(12kk5e) where k is the size of the solution and e is the length of the input formula. 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(12kk5e) where k is the size of the smallest q-Horn deletion backdoor set, with e being the length of the input formula.
Andrii Dmytryshyn - One of the best experts on this subject based on the ideXlab platform.
-
Generic Skew-Symmetric matrix polynomials with fixed rank and fixed odd grade
arXiv: Rings and Algebras, 2017Co-Authors: Andrii Dmytryshyn, Froilán M. DopicoAbstract:We show that the set of $m \times m$ complex Skew-Symmetric matrix polynomials of odd grade $d$, i.e., of degree at most $d$, and (normal) rank at most $2r$ is the closure of the single set of matrix polynomials with the certain, explicitly described, complete eigenstructure. This complete eigenstructure corresponds to the most generic $m \times m$ complex Skew-Symmetric matrix polynomials of odd grade $d$ and rank at most $2r$. In particular, this result includes the case of Skew-Symmetric matrix pencils ($d=1$).
-
Structure preserving stratification of Skew-Symmetric matrix polynomials
Linear Algebra and its Applications, 2017Co-Authors: Andrii DmytryshynAbstract:We study how elementary divisors and minimal indices of a Skew-Symmetric matrix polynomial of odd degree may change under small perturbations of the matrix coefficients. We investigate these change ...
-
Orbit closure hierarchies of Skew-Symmetric matrix pencils
SIAM Journal on Matrix Analysis and Applications, 2014Co-Authors: Andrii Dmytryshyn, Bo KågströmAbstract:We study how small perturbations of a Skew-Symmetric matrix pencil may change its canonical form under congruence. This problem is also known as the stratification problem of Skew-Symmetric matrix pencil orbits and bundles. In other words, we investigate when the closure of the congruence orbit (or bundle) of a Skew-Symmetric matrix pencil contains the congruence orbit (or bundle) of another Skew-Symmetric matrix pencil. The developed theory relies on our main theorem stating that a Skew-Symmetric matrix pencil $A-\lambda B$ can be approximated by pencils strictly equivalent to a Skew-Symmetric matrix pencil $C-\lambda D$ if and only if $A-\lambda B$ can be approximated by pencils congruent to $C-\lambda D$.
-
ORBIT CLOSURE HIERARCHIES OF Skew-Symmetric
2014Co-Authors: Matrix Pencils, Andrii Dmytryshyn, Bo KAbstract:We study how small perturbations of a Skew-Symmetric matrix pencil may change its canonical form under congruence. This problem is also known as the stratification problem of Skew-Symmetric matrix pencil orbits and bundles. In other words, we investigate when the closure of the congruence orbit (or bundle) of a Skew-Symmetric matrix pencil contains the congruence orbit (or bundle) of another Skew-Symmetric matrix pencil. The developed theory relies on our main theorem stating that a Skew-Symmetric matrix pencil A − λB can be approximated by pencils strictly equivalent to a Skew-Symmetric matrix pencil C − λD if and only if A − λB can be approximated by pencils congruent to C − λD.
-
Orbit closure hierarchies of Skew-Symmetric matrix pencils
SIAM Journal on Matrix Analysis and Applications, 2014Co-Authors: Andrii Dmytryshyn, Bo KågströmAbstract:We study how small perturbations of a Skew-Symmetric matrix pencil may change its canonical form under congruence. This problem is also known as the stratification problem of Skew-Symmetric matrix ...
Alexander V. Karzanov - One of the best experts on this subject based on the ideXlab platform.
-
Maximum Skew-Symmetric flows and matchings
Mathematical Programming, 2004Co-Authors: Andrew V. Goldberg, Alexander V. KarzanovAbstract:The maximum integer Skew-Symmetric flow problem (MSFP) generalizes both the maximum flow and maximum matching problems. It was introduced by Tutte [28] in terms of self-conjugate flows in antiSymmetrical digraphs. He showed that for these objects there are natural analogs of classical theoretical results on usual network flows, such as the flow decomposition, augmenting path, and max-flow min-cut theorems. We give unified and shorter proofs for those theoretical results. We then extend to MSFP the shortest augmenting path method of Edmonds and Karp [7] and the blocking flow method of Dinits [4], obtaining algorithms with similar time bounds in general case. Moreover, in the cases of unit arc capacities and unit “node capacities” our blocking Skew-Symmetric flow algorithm has time bounds similar to those established in [8, 21] for Dinits’ algorithm. In particular, this implies an algorithm for finding a maximum matching in a nonbipartite graph in * time, which matches the time bound for the algorithm of Micali and Vazirani [25]. Finally, extending a clique compression technique of Feder and Motwani [9] to particular Skew-Symmetric graphs, we speed up the implied maximum matching algorithm to run in * time, improving the best known bound for dense nonbipartite graphs. Also other theoretical and algorithmic results on Skew-Symmetric flows and their applications are presented.
-
Maximum Skew-Symmetric Flows and Matchings
arXiv: Combinatorics, 2003Co-Authors: Andrew V. Goldberg, Alexander V. KarzanovAbstract:The maximum integer Skew-Symmetric flow problem (MSFP) generalizes both the maximum flow and maximum matching problems. It was introduced by Tutte in terms of self-conjugate flows in antiSymmetrical digraphs. He showed that for these objects there are natural analogs of classical theoretical results on usual network flows, such as the flow decomposition, augmenting path, and max-flow min-cut theorems. We give unified and shorter proofs for those theoretical results. We then extend to MSFP the shortest augmenting path method of Edmonds and Karp and the blocking flow method of Dinits, obtaining algorithms with similar time bounds in general case. Moreover, in the cases of unit arc capacities and unit ``node capacities'' the blocking Skew-Symmetric flow algorithm has time bounds similar to those established in Even and Tarjan (1975) and Karzanov (1973) for Dinits' algorithm. In particular, this implies an algorithm for finding a maximum matching in a nonbipartite graph in $O(\sqrt{n}m)$ time, which matches the time bound for the algorithm of Micali and Vazirani. Finally, extending a clique compression technique of Feder and Motwani to particular Skew-Symmetric graphs, we speed up the implied maximum matching algorithm to run in $O(\sqrt{n}m\log(n^2/m)/\log{n})$ time, improving the best known bound for dense nonbipartite graphs. Also other theoretical and algorithmic results on Skew-Symmetric flows and their applications are presented.
-
Path problems in Skew-Symmetric graphs
Combinatorica, 1996Co-Authors: Andrew V. Goldberg, Alexander V. KarzanovAbstract:We study path problems in Skew-Symmetric graphs. These problems generalize the standard graph reachability and shortest path problems. We establish combinatorial solvability criteria and duality relations for the Skew-Symmetric path problems and use them to design efficient algorithms for these problems. The algorithms presented are competitive with the fastest algorithms for the standard problems.
-
ESA - Maximum Skew-Symmetric Flows
Lecture Notes in Computer Science, 1995Co-Authors: Andrew V. Goldberg, Alexander V. KarzanovAbstract:We introduce the maximum Skew-Symmetric flow problem which generalizes flow and matching problems. We develop a theory of Skew-Symmetric flows that is parallel to the classical flow theory. We use the newly developed theory to extend, in a natural way, the blocking flow method of Dinitz to the Skew-Symmetric flow case. In the special case of the Skew-Symmetric flow problem that corresponds to cardinality matching, our algorithm is simpler and more efficient than the corresponding matching algorithm.
-
SODA - Path problems in Skew-Symmetric graphs
1994Co-Authors: Andrew V. Goldberg, Alexander V. KarzanovAbstract:We study path problems in Skew-Symmetric graphs. These problems generalize the standard graph reachability and shortest path problems. We establish combinatorial solvability criteria and duality relations for the Skew-Symmetric path problems and use them to design efficient algorithms for these problems. The algorithms presented are competitive with the fastest algorithms for the standard problems.
