Skew-symmetric graph

A skew-symmetric graph is a directed graph that is isomorphic to its own transposed graph , a graph formed by inverting all arcs with an isomorphism that is an involution without fixed points . Skew-symmetric graphs are identical to double covers of .

Skew-symmetric graphs were introduced first under the name Tatt ^[1] as antisymmetric digraphs , later Zelinka used them under the name of double covering graphs of polar graphs ^[2] , and later Zaslavsky used them under the name of double-covering graphs of bidirectional graphs ^[3] . They arise in modeling the search for alternating paths and cycles in algorithms for finding matching in graphs, for testing that the configuration in the Life game can be decomposed into smaller components, in graph visualization and in used to effectively solve the problem .

Content

Definition

As defined, for example, by Goldberg and Karzanov ^[4] , the skew-symmetric graph G is a directed graph together with a function $\sigma$ ${\ displaystyle \ sigma}$ mapping the vertices of the graph G to other vertices of G and satisfying the properties:

For any vertex $v,\sigma (v)\neq v$ ${\ displaystyle v, \ sigma (v) \ neq v}$ ,
For any vertex $v,\sigma (\sigma (v))=v$ ${\ displaystyle v, \ sigma (\ sigma (v)) = v}$ ,
For any arc $(u,v),(\sigma (v),\sigma (u))$ ${\ displaystyle (u, v), (\ sigma (v), \ sigma (u))}$ must also be an arc.

You can use the third property to expand $\sigma$ ${\ displaystyle \ sigma}$ to the inverse function of the orientation of the arcs of the graph G.

The transposed graph of G is a graph formed by inverting each edge of G , and $\sigma$ ${\ displaystyle \ sigma}$ defines an isomorphism from G to a transposed graph. However, in the skew-symmetric graph there is an additional requirement that the isomorphism translates each vertex to another vertex, not allowing the vertex to map into itself, or to group more than two vertices in the isomorphism cycle.

It is said that a path or cycle in a skew-symmetric graph is regular if, for each vertex v of the path or cycle, the corresponding vertex $\sigma (v)$ ${\ displaystyle \ sigma (v)}$ not part of a path or cycle.

Examples

Any oriented path with an even number of vertices is skew-symmetric according to the symmetry that exchanges the two ends of the path. However, paths with an odd number of vertices are not skew-symmetric, since the symmetry of the reverse orientation of this graph maps the middle vertex of this graph into itself, which is not allowed for skew-symmetric graphs.

Similarly, an oriented cycle is skew-symmetric if and only if it has an even number of vertices. In this case, the number of different mappings $\sigma$ ${\ displaystyle \ sigma}$ which realize the oblique symmetry of the graph is equal to half the length of the cycle.

Polar graphs and directional arrows, double-covering graphs, and bidirectional graphs

A skew-symmetric graph can be equivalently defined as the double-covering graph of the polar graph (introduced by Zelinka ^[5] ^[6] and which Cook called the graphs of directional arrows ^[7] ^[8] ), which are undirected graphs and in which the edges adjacent to each vertex are broken into two subsets. Each vertex of the polar graph corresponds to two vertices of the skew-symmetric graph, and each edge of the polar graph corresponds to two edges of the skew-symmetric graph. Goldberg and Karzanov ^[4] used this equivalence to model matching problems in terms of skew-symmetric graphs. In such an application, two subsets of edges at each vertex are included in the matching and edges not included in it. Zelinka (according to F. Zaitek) and Cook visualized the vertices of the polar graph as points at which several meet - if a train enters the directional arrow on a railway that comes from one direction, it must exit through the track in another direction . The problem of finding non-intersecting smooth curves between given points of a railway track arises when checking whether some kind of graph visualization is valid ^[9] , and can be modeled as a search for a regular track in a skew-symmetric graph.

A closely related concept is the Edmonds and Johnson ^[10] (a “polarized graph” in the terminology of Zelinka ^[5] ^[6] ), a graph in which each of the two ends of any edge can be either a head or a tail, independently from the other end. A bidirectional graph can be interpreted as a polar graph if we divide the edges of each vertex by the type of end of the edge at this vertex - head or tail; However, the exchange of roles of heads and tails in a separate vertex (“switching” the vertices in the terminology of Zaslavsky ^[3] ) gives another bi-directional graph, but the same polar graph.

For correspondence between bidirectional graphs and skew-symmetric graphs, see articles by Zaslavsky ^[11] or Babenko ^[12] .

To form a double-covering graph (i.e., the corresponding skew-symmetric graph) from the polar graph G , we create from each vertex v of the graph G two vertices, v ₀ and v ₁ , and let $\sigma (v_{i})=v_{1-i}$ ${\ displaystyle \ sigma (v_ {i}) = v_ {1-i}}$ . For each rib $e=(u,v)$ ${\ displaystyle e = (u, v)}$ of the graph G, we create two oriented edges (arcs) in the covering graph, one of u in v and one of v in u . If e is in the first subset of edges in v , these two arcs come from $u_{0}$ ${\ displaystyle u_ {0}}$ in v ₀ and from v ₁ to u ₁ , but if e belongs to another subset, the arcs will be from u ₀ to v ₁ and from v ₀ to u ₁ . In the opposite direction, if a skew-symmetric graph G is given , it is possible to form a polar graph that has one vertex for any corresponding pair of vertices of the graph G and one unoriented edge for each corresponding pair of edges in G. The non-oriented edges at each vertex of the polar graph can be divided into two subsets according to which vertex of the original graph the arc leaves and to which it enters.

A regular path or cycle of a skew-symmetric graph corresponds to a path or cycle in a polar graph that uses a maximum of one edge from each subset of edges at each of its vertices.

Matching

When constructing matching in an undirected graph, it is important to find an alternating path , a path through vertices that begins and ends at vertices that do not belong to the matching, and whose edges at odd positions of the path do not belong to this partial matching, and the edges at even positions of the path are matching edges. By removing the edges belonging to the matching from this path from the matching and adding the remaining edges of the path to it, we can increase the matching size. Similarly, cycles in which edges from matching and non-matching alternate are important in weighted matching problems. As Goldberg and Karzanov ^[4] showed, an alternating path or cycle in an undirected graph can be modeled as a regular path or cycle in a skew-symmetric oriented graph. To create a skew-symmetric graph from an undirected graph G with an existing matching M , we consider the graph G as a path arrow graph in which the edges at each vertex are divided into belonging to the combination and not belonging. The alternating path in the graph G is then the regular path in this graph of the directional arrows, and the alternating cycle in the graph of G is the regular cycle in the graph of the directional arrows.

Goldberg and Karzanov ^[4] generalized alternating path algorithms to show that the existence of a regular path between any two vertices of a skew-symmetric graph can be verified in linear time. If, in addition, a non-negative length function is given on the edges of the graph, which assigns equal lengths to the edge e and the edge $\sigma (e)$ ${\ displaystyle \ sigma (e)}$ , the shortest regular path connecting a given pair of nodes in a skew-symmetric graph with m edges and n vertices can be found in time $O(m\log n)$ ${\ displaystyle O (m \ log n)}$ . If the length function can take negative values, the existence of a negative regular cycle can be checked in polynomial time.

In addition to problems with paths arising when working with matching, skew-symmetric generalizations of the maximum flow and minimum cut theorem were also studied ^[13] ^[1] .

Game Theory Theory

Cook ^[8] showed that the configuration in the game “Life” can be divided into two smaller configurations if and only if the graph of the associated graph of directional arrows contains a regular cycle. As he showed, for graphs of directional arrows containing no more than three edges per vertex, this can be checked in polynomial time by removing bridges one by one (edges, the removal of which makes the graph disconnected) and vertices in which all edges belong to one part of the partition , while there is the possibility of such simplifications. If as a result we get an empty graph, there is no regular cycle in the graph. Otherwise, a regular loop can be found in any component that does not contain bridges. The search for bridges in this algorithm can be carried out efficiently using the Sorup dynamic algorithm ^[14] .

A similar technique for removing bridges in the context of matching was previously considered by Gabov, Kaplan and Taryan ^[15] .

Feasibility

. Its oblique symmetry can be detected by turning the graph 180 degrees and turning all the edges.

An instance of the , that is, a Boolean expression in conjunctive normal form with two variables or the negation of variables, can be converted into an by replacing each expression $\scriptstyle u\lor v$ ${\ displaystyle \ scriptstyle u \ lor v}$ two implications $\scriptstyle (\lnot u)\Rightarrow v$ ${\ displaystyle \ scriptstyle (\ lnot u) \ Rightarrow v}$ and $\scriptstyle (\lnot v)\Rightarrow u$ ${\ displaystyle \ scriptstyle (\ lnot v) \ Rightarrow u}$ . This graph has a vertex for each variable or negation of the variable and an oriented edge for each implication. The graph, by construction, is skew-symmetric with the correspondence $\sigma$ ${\ displaystyle \ sigma}$ which maps each variable to its negation. As Asvall, Plass, and Taryan ^[16] showed, finding a performing set of values for an instance of a 2-satisfiability problem is equivalent to splitting this output graph into two subsets of vertices, S and $\sigma (S)$ ${\ displaystyle \ sigma (S)}$ so that no arc begins at S and ends at $\sigma (S)$ ${\ displaystyle \ sigma (S)}$ . If such a partition exists, a performing set of values can be obtained by assigning true to each variable from S and false to each variable from $\sigma (S)$ ${\ displaystyle \ sigma (S)}$ . This can be done if and only if no component of the strongly connected graph contains both the vertex v and its complementary vertex $\sigma (v)$ ${\ displaystyle \ sigma (v)}$ . If two vertices belong to the same component of strong connection, the corresponding variables or their negations are necessarily equal to each other in any performing set of values of the instance of the 2-satisfiability problem. The total time for checking for strong connectivity and finding the partition of the output graph is linear with the size of the given 2-CNF expression.

Recognition

The problem of recognizing whether a given directed graph is skew-symmetric is NP-complete , according to the result of Lalonde ^[17] , that the NP-complete problem is to find the inverse color of an involution in a bipartite graph . Such an involution exists if and only if the oriented graph defined by the orientation of each edge from one color class to another is skew-symmetric, so checking the skew-symmetry of this oriented graph is difficult. This complexity does not affect the path finding algorithms for skew-symmetric graphs, since these algorithms assume that the skew-symmetric structure is specified as part of the input to the algorithm, and is not derived only from the graph.

Notes

↑ ¹ ² Tutte, 1967 .
↑ Zelinka, 1976b .
↑ ¹ ² Zaslavsky, 1991 .
↑ ¹ ² ³ ⁴ Goldberg, Karzanov, 1996 .
↑ ¹ ² Zelinka, 1974 .
↑ ¹ ² Zelinka, 1976a .
↑ The graph of directional arrows comes from the representation of the graph as an analogue of railway tracks with the junctions of individual branches as switching arrows.
↑ ¹ ² Cook, 2003 .
↑ Hui, Schaefer, Štefankovič, 2004 .
↑ Edmonds, Johnson, 1970 .
↑ Zaslavsky, 1991 , p. Section Section 5.
↑ Babenko, 2006 .
↑ Goldberg, Karzanov, 2004 .
↑ Thorup, 2000 .
↑ Gabow, Kaplan, Tarjan, 1999 .
↑ Aspvall, Plass, Tarjan, 1979 .
↑ Lalonde, 1981 .

Literature

Bengt Aspvall, Michael F. Plass, Robert E. Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas // Information Processing Letters. - 1979. - T. 8 , no. 3 . - S. 121–123 . - DOI : 10.1016 / 0020-0190 (79) 90002-4 .
Maxim A. Babenko. Acyclic bidirected and skew-symmetric graphs: algorithms and structure // Computer Science - Theory and Applications. - Springer-Verlag, 2006. - T. 3967. - S. 23–34. - (Lecture Notes in Computer Science). - ISBN 978-3-540-34166-6 . - DOI : 10.1007 / 11753728_6 .
Norman L. Biggs. Algebraic Graph Theory. - Cambridge University Press, 1974.
Matthew Cook. Still life theory // New Constructions in Cellular Automata. - Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press, 2003. - S. 93–118. .
Jack Edmonds, Ellis L. Johnson. Matching: a well-solved class of linear programs // Combinatorial Structures and their Applications: Proceedings of the Calgary Symposium, June 1969. - Gordon and Breach, 1970 .. Reprinted in “Combinatorial Optimization - Eureka, You Shrink!”, Springer-Verlag, Lecture Notes in Computer Science 2570, 2003, pp. 27-30, DOI : 10.1007 / 3-540-36478-1_3 .
Harold N. Gabow, Haim Kaplan, Robert E. Tarjan . Unique maximum matching algorithms // Proc. 31st ACM Symp. Theory of Computing (STOC). - 1999. - S. 70–78. - ISBN 1-58113-067-8 . - DOI : 10.1145 / 301250.301273 .
Andrew V. Goldberg, Alexander V. Karzanov. Path problems in skew-symmetric graphs // Combinatorica. - 1996. - T. 16 , no. 3 . - S. 353–382 . - DOI : 10.1007 / BF01261321 .
Andrew V. Goldberg, Alexander V. Karzanov. Maximum skew-symmetric flows and matchings // Mathematical programming. - 2004. - T. 100 , no. 3 . - S. 537-568 . - DOI : 10.1007 / s10107-004-0505-z . - arXiv : math / 0304290 .
Peter Hui, Marcus Schaefer, Daniel Štefankovič. Train tracks and confluent drawings // Proc. 12th Int. Symp Graph Drawing . - Springer-Verlag, 2004. - T. 3383. - S. 318–328. - (Lecture Notes in Computer Science).
François Lalonde. Le problème d'étoiles pour graphes est NP-complet // Discrete Mathematics. - 1981. - T. 33 , no. 3 . - S. 271–280 . - DOI : 10.1016 / 0012-365X (81) 90271-5 .
Mikkel Thorup. Near-optimal fully [ sic ]^[*] dynamic graph connectivity // Proc. 32nd ACM Symposium on Theory of Computing . - 2000. - S. 343-350. - ISBN 1-58113-184-4 . - DOI : 10.1145 / 335305.335345 .
Tutte WT Antisymmetrical digraphs // Canadian Journal of Mathematics. - 1967. - T. 19 . - S. 1101–1117 . - DOI : 10.4153 / CJM-1967-101-8 .
Thomas Zaslavsky. Signed graphs // Discrete Applied Mathematics. - 1982. - T. 4 . - S. 47–74 . - DOI : 10.1016 / 0166-218X (82) 90033-6 .
Thomas Zaslavsky. Orientation of signed graphs // European Journal of Combinatorics. - 1991 .-- T. 12 . - S. 361-375 . - DOI : 10.1016 / s0195-6698 (13) 80118-7 .
Bohdan Zelinka. Polar graphs and railway traffic // Aplikace Matematiky. - 1974.- T. 19 . - S. 169–176 .
Bohdan Zelinka. Isomorphisms of polar and polarized graphs // Czechoslovak Mathematical Journal. - 1976a. - T. 26 . - S. 339–351 .
Bohdan Zelinka. Analoga of Menger's theorem for polar and polarized graphs // Czechoslovak Mathematical Journal. - 1976b. - T. 26 . - S. 352-360 .

[_200f19d9750c6a56-1] ¹ ² Tutte, 1967 .

[_5c72b2555d2dbf58-2] Zelinka, 1976b .

[_6662c8a325e0043d-3] ¹ ² Zaslavsky, 1991 .

[_88d81655bf5a607c-4] ¹ ² ³ ⁴ Goldberg, Karzanov, 1996 .

[_7cfdba58f8c507b4-5] ¹ ² Zelinka, 1974 .

[_755aa3fd8577d3cf-6] ¹ ² Zelinka, 1976a .

[7] The graph of directional arrows comes from the representation of the graph as an analogue of railway tracks with the junctions of individual branches as switching arrows.

[_5f887501e3f972c8-8] ¹ ² Cook, 2003 .

[_3f1bd185f7348ef9-9] Hui, Schaefer, Štefankovič, 2004 .

[_5ac0de6e4f4d02ad-10] Edmonds, Johnson, 1970 .

[_29ee866867b839e5-11] Zaslavsky, 1991 , p. Section Section 5.

[_9321632990fcf26f-12] Babenko, 2006 .

[_89835223828d6995-13] Goldberg, Karzanov, 2004 .

[_3375119d41b7ec1b-14] Thorup, 2000 .

[_e1628eb8892bf3dc-15] Gabow, Kaplan, Tarjan, 1999 .

[_449699a7178c37f9-16] Aspvall, Plass, Tarjan, 1979 .

[_b7e0428a1c7a151f-17] Lalonde, 1981 .