Editing Shannon switching game (section)

==Computational complexity==

An explicit solution for the undirected switching game was found in 1964 for any such game using [[matroid]] theory. ''Short'' should aim for a position in which there exists a set of vertices <math>S</math> including the two distinguished vertices, as well as two disjoint subsets of the remaining unchosen edges supported on <math>S</math>, such that either of the two subsets (together with already chosen edges) would connect all vertices in <math>S</math>. If ''Short'' can make a move that results in a position with this property, then ''Short'' can win regardless of what the other player does; otherwise, ''Cut'' can win.<ref name=lehman>{{cite journal
 | last = Lehman | first = Alfred
 | issue = 4
 | journal = Journal of the Society for Industrial and Applied Mathematics
 | jstor = 2946344
 | mr = 0173250
 | pages = 687–725
 | title = A solution of the Shannon switching game
 | volume = 12
 | year = 1964| doi = 10.1137/0112059
 }}</ref>
<ref name=mansfield>{{cite journal
 | issue = 3
 | last=Mansfield | first = Richard
 | journal = The American Mathematical Monthly
 | pages = 250–252
 | title = Strategies for the Shannon switching game
 | volume = 103
 | year = 1996
| doi=10.1080/00029890.1996.12004732 }}
</ref>

Unlike some other connection games, which can be [[PSPACE]] hard,<ref>{{cite journal | url=http://hex.kosmanor.com/hex/jacm23/t710.html | title=A Combinatorial Problem Which is Complete in Polynomial Space | last=Even|first= S. | authorlink= Shimon Even | journal=[[Journal of the ACM]] |date=October 1976 | volume=23 | issue=4 | pages=710–719 | doi=10.1145/321978.321989| s2cid=8845949 | doi-access=free }}</ref><ref>{{cite journal
 | last = Reisch | first = Stefan
 | doi = 10.1007/BF00288964
 | issue = 2
 | journal = [[Acta Informatica]]
 | mr = 599616
 | pages = 167–191
 | title = Hex ist PSPACE-vollständig
 | volume = 15
 | year = 1981| s2cid = 9125259
 }}</ref> optimal moves for the undirected switching game can be found in [[polynomial time]] per move. After removing from the graph the edges chosen by ''Cut'', and contracting the edges chosen by ''Short'', the resulting graph is a [[minor (graph theory)|minor]] of the starting graph. The problem of testing for the existence of two disjoint trees, each connecting the distinguished vertices, can be represented as a [[matroid partitioning]] problem, which can be solved in polynomial time. Alternatively, it is possible to solve the same problem using [[Network flow problem|network flow]] algorithms.