Skew-symmetric graph

Last updated February 08, 2024

In graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges, under an isomorphism that is an involution without any fixed points. Skew-symmetric graphs are identical to the double covering graphs of bidirected graphs.

Skew-symmetric graphs were first introduced under the name of antisymmetrical digraphs by Tutte (1967), later as the double covering graphs of polar graphs by Zelinka (1976b), and still later as the double covering graphs of bidirected graphs by Zaslavsky (1991). They arise in modeling the search for alternating paths and alternating cycles in algorithms for finding matchings in graphs, in testing whether a still life pattern in Conway's Game of Life may be partitioned into simpler components, in graph drawing, and in the implication graphs used to efficiently solve the 2-satisfiability problem.

Definition

As defined, e.g., by Goldberg & Karzanov (1996), a skew-symmetric graph G is a directed graph, together with a function σ mapping vertices of G to other vertices of G, satisfying the following properties:

For every vertex v, σ(v) ≠ v,
For every vertex v, σ(σ(v)) = v,
For every edge (u,v), (σ(v),σ(u)) must also be an edge.

One may use the third property to extend σ to an orientation-reversing function on the edges of G.

The transpose graph of G is the graph formed by reversing every edge of G, and σ defines a graph isomorphism from G to its transpose. However, in a skew-symmetric graph, it is additionally required that the isomorphism pair each vertex with a different vertex, rather than allowing a vertex to be mapped to itself by the isomorphism or to group more than two vertices in a cycle of isomorphism.

A path or cycle in a skew-symmetric graph is said to be regular if, for each vertex v of the path or cycle, the corresponding vertex σ(v) is not part of the path or cycle.

Examples

Every directed path graph with an even number of vertices is skew-symmetric, via a symmetry that swaps the two ends of the path. However, path graphs with an odd number of vertices are not skew-symmetric, because the orientation-reversing symmetry of these graphs maps the center vertex of the path to itself, something that is not allowed for skew-symmetric graphs.

Similarly, a directed cycle graph is skew-symmetric if and only if it has an even number of vertices. In this case, the number of different mappings σ that realize the skew symmetry of the graph equals half the length of the cycle.

Polar/switch graphs, double covering graphs, and bidirected graphs

A skew-symmetric graph may equivalently be defined as the double covering graph of a polar graph or switch graph,^[1] which is an undirected graph in which the edges incident to each vertex are partitioned 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. This equivalence is the one used by Goldberg & Karzanov (1996) to model problems of matching in terms of skew-symmetric graphs; in that application, the two subsets of edges at each vertex are the unmatched edges and the matched edges. Zelinka (following F. Zitek) and Cook visualize the vertices of a polar graph as points where multiple tracks of a train track come together: if a train enters a switch via a track that comes in from one direction, it must exit via a track in the other direction. The problem of finding non-self-intersecting smooth curves between given points in a train track comes up in testing whether certain kinds of graph drawings are valid.^[2] and may be modeled as the search for a regular path in a skew-symmetric graph.

A closely related concept is the bidirected graph or polarized graph,^[3] a graph in which each of the two ends of each edge may be either a head or a tail, independently of the other end. A bidirected graph may be interpreted as a polar graph by letting the partition of edges at each vertex be determined by the partition of endpoints at that vertex into heads and tails; however, swapping the roles of heads and tails at a single vertex ("switching" the vertex) produces a different bidirected graph but the same polar graph.^[4]

To form the double covering graph (i.e., the corresponding skew-symmetric graph) from a polar graph G, create for each vertex v of G two vertices v₀ and v₁, and let σ(v_i) = v_1 − i. For each edge e = (u,v) of G, create two directed edges in the covering graph, one oriented from u to v and one oriented from v to u. If e is in the first subset of edges at v, these two edges are from u₀ into v₀ and from v₁ into u₁, while if e is in the second subset, the edges are from u₀ into v₁ and from v₀ into u₁. In the other direction, given a skew-symmetric graph G, one may form a polar graph that has one vertex for every corresponding pair of vertices in G and one undirected edge for every corresponding pair of edges in G. The undirected edges at each vertex of the polar graph may be partitioned into two subsets according to which vertex of the polar graph they go out of and come into.

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

Matching

In constructing matchings in undirected graphs, it is important to find alternating paths, paths of vertices that start and end at unmatched vertices, in which the edges at odd positions in the path are not part of a given partial matching and in which the edges at even positions in the path are part of the matching. By removing the matched edges of such a path from a matching, and adding the unmatched edges, one can increase the size of the matching. Similarly, cycles that alternate between matched and unmatched edges are of importance in weighted matching problems. An alternating path or cycle in an undirected graph may be modeled as a regular path or cycle in a skew-symmetric directed graph.^[5] To create a skew-symmetric graph from an undirected graph G with a specified matching M, view G as a switch graph in which the edges at each vertex are partitioned into matched and unmatched edges; an alternating path in G is then a regular path in this switch graph and an alternating cycle in G is a regular cycle in the switch graph.

Goldberg & Karzanov (1996) generalized alternating path algorithms to show that the existence of a regular path between any two vertices of a skew-symmetric graph may be tested in linear time. Given additionally a non-negative length function on the edges of the graph that assigns the same length to any edge e and to σ(e), the shortest regular path connecting a given pair of nodes in a skew-symmetric graph with m edges and n vertices may be tested in time O(m log n). If the length function is allowed to have negative lengths, the existence of a negative regular cycle may be tested in polynomial time.

Along with the path problems arising in matchings, skew-symmetric generalizations of the max-flow min-cut theorem have also been studied.^[6]

Still life theory

Cook (2003) shows that a still life pattern in Conway's Game of Life may be partitioned into two smaller still lifes if and only if an associated switch graph contains a regular cycle. As he shows, for switch graphs with at most three edges per vertex, this may be tested in polynomial time by repeatedly removing bridges (edges the removal of which disconnects the graph) and vertices at which all edges belong to a single partition until no more such simplifications may be performed. If the result is an empty graph, there is no regular cycle; otherwise, a regular cycle may be found in any remaining bridgeless component. The repeated search for bridges in this algorithm may be performed efficiently using a dynamic graph algorithm of Thorup (2000).

Similar bridge-removal techniques in the context of matching were previously considered by Gabow, Kaplan & Tarjan (1999).

Satisfiability

An instance of the 2-satisfiability problem, that is, a Boolean expression in conjunctive normal form with two variables or negations of variables per clause, may be transformed into an implication graph by replacing each clause $\scriptstyle u\lor v$ by the two implications $\scriptstyle (\lnot u)\Rightarrow v$ and $\scriptstyle (\lnot v)\Rightarrow u$ . This graph has a vertex for each variable or negated variable, and a directed edge for each implication; it is, by construction, skew-symmetric, with a correspondence σ that maps each variable to its negation. As Aspvall, Plass & Tarjan (1979) showed, a satisfying assignment to the 2-satisfiability instance is equivalent to a partition of this implication graph into two subsets of vertices, S and σ(S), such that no edge starts in S and ends in σ(S). If such a partition exists, a satisfying assignment may be formed by assigning a true value to every variable in S and a false value to every variable in σ(S). This may be done if and only if no strongly connected component of the graph contains both some vertex v and its complementary vertex σ(v). If two vertices belong to the same strongly connected component, the corresponding variables or negated variables are constrained to equal each other in any satisfying assignment of the 2-satisfiability instance. The total time for testing strong connectivity and finding a partition of the implication graph is linear in the size of the given 2-CNF expression.

Recognition

It is NP-complete to determine whether a given directed graph is skew-symmetric, by a result of Lalonde (1981) that it is NP-complete to find a color-reversing involution in a bipartite graph. Such an involution exists if and only if the directed graph given by orienting each edge from one color class to the other is skew-symmetric, so testing skew-symmetry of this directed graph is hard. This complexity does not affect path-finding algorithms for skew-symmetric graphs, because these algorithms assume that the skew-symmetric structure is given as part of the input to the algorithm rather than requiring it to be inferred from the graph alone.

Notes

↑ Polar graphs were introduced by Zelinka (1974) and Zelinka (1976a), and called switch graphs by Cook (2003).
↑ Hui, Schaefer & Štefankovič (2004).
↑ Bidirected graphs were introduced by Edmonds & Johnson (1970), and called polarized graphs by Zelinka (1974) and Zelinka (1976a)
↑ Zaslavsky (1991), Section 5; Babenko (2006).
↑ Goldberg & Karzanov (1996).
↑ Goldberg & Karzanov (2004); Tutte (1967).

Related Research Articles

<span class="mw-page-title-main">Hypergraph</span> Generalization of graph theory

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

<span class="mw-page-title-main">Component (graph theory)</span> Maximal subgraph whose vertices can reach each other

In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

In the mathematical discipline of graph theory, the line graph of an undirected graph $G$ is another graph $L(G)$ that represents the adjacencies between edges of $G$ . $L(G)$ is constructed in the following way: for each edge in $G$ , make a vertex in $L(G)$ ; for every two edges in $G$ that have a vertex in common, make an edge between their corresponding vertices in $L(G)$ .

<span class="mw-page-title-main">Strongly connected component</span> Partition of a graph whose components are reachable from all vertices

In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time (that is, Θ(V + E)).

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges connecting pairs of vertices in that subset.

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is named after A. L. Dulmage and Nathan Mendelsohn, who published it in 1958. A generalization to any graph is the Edmonds–Gallai decomposition, using the Blossom algorithm.

In computer science, the Hopcroft–Karp algorithm is an algorithm that takes a bipartite graph as input and produces a maximum-cardinality matching as output — a set of as many edges as possible with the property that no two edges share an endpoint. It runs in $time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes, and for sparse random graphs it runs in time with high probability.$

In graph theory, a mathematical discipline, a factor-critical graph is a graph with $n$ vertices in which every subgraph of $n - 1$ vertices has a perfect matching.

In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann. The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.

<span class="mw-page-title-main">Handshaking lemma</span> Every graph has evenly many odd vertices

In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees equals twice the number of edges in the graph. Both results were proven by Leonhard Euler in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.

<span class="mw-page-title-main">Pseudoforest</span> Graph with one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity.

In mathematics, and more specifically in graph theory, a directed graph is a graph that is made up of a set of vertices connected by directed edges, often called arcs.

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.

References

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Polar graphs were introduced by Zelinka (1974) and Zelinka (1976a), and called switch graphs by Cook (2003).

[FOOTNOTEHuiSchaeferŠtefankovič2004-2] Hui, Schaefer & Štefankovič (2004).

[3] Bidirected graphs were introduced by Edmonds & Johnson (1970), and called polarized graphs by Zelinka (1974) and Zelinka (1976a)

[4] Zaslavsky (1991), Section 5; Babenko (2006).

[FOOTNOTEGoldbergKarzanov1996-5] Goldberg & Karzanov (1996).

[6] Goldberg & Karzanov (2004); Tutte (1967).

[1]

[2]

[3]

[4]

[5]

[6]

Graph families defined by their automorphisms
distance-transitive	→	distance-regular	←	strongly regular
↓
symmetric (arc-transitive)	←	t-transitive, $t \geq 2$		skew-symmetric
↓
_{(if connected)} vertex- and edge-transitive	→	edge-transitive and regular	→	edge-transitive
↓		↓		↓
vertex-transitive	→	regular	→	_{(if bipartite)} biregular
↑
Cayley graph	←	zero-symmetric		asymmetric