Set-stabilizer problem

This article describes a group-finding problem, that is, a problem where we have to explicitly find a generating set of a group that is specified through certain conditions

This problem is polynomial-time equivalent to the following basic problem: Group intersection problem

Description

A group $G$ acting faithfully on a finite set $S$ , is specified by a generating set $A$ (where each element of $A$ is specified as a permutation)
A subset $T$ of $S$ is given

We need to find the subgroup of $G$ comprising those elements that map every element of $T$ to inside $T$ .

The set stabilizer problem is polynomial-time equivalent to the following decision problems:

The set transporter problem: This is a decision problem which asks whether, for a group action on a set, one given subset can be transported to another. For full proof, refer: Set transporter PTIME equals set stabilizer
The conjugacy problem: This is a decision problem which asks whether two given elements in the whole symmetric group are conjugate in the subgroup $G$ .For full proof, refer: Conjugacy problem PTIME equals set stabilizer
The group factorization problem: This is a decision problem that, given two subgroups $G$ and $H$ of the symmetric group, and an element $x$ of the symmetric group, asks whether $x$ is in $GH$ .

Group intersection problem: The set stabilizer problem can be viewed as a group intersection problem where one group is $G$ and the other group is $Sym(T)$ × $Sym(T^{c})$ (that is, the stabilizer of $T$ in the whole of $Sym(S)$ . The converse is also true: any group intersection problem can be viewed as a set stabilizer problem for the diagonal in an action on the square space. For full proof, refer: Group intersection PTIME equals set stabilizer
The partition stabilizer problem: Here, instead of giving a subset $T$ of $S$ , we give a partition of $S$ viz $S$ as a disjoint union of subsets, and are required to find the subgroup of $G$ comprising those elements that preserve the partition (though they may not preserve individual sets in the partition).
The centralizer-finding problem: This is a group-finding problem that takes as input an element of the symmetric group on a finite set and outputs a generating set for the centralizer of that element.

Graph automorphism-finding: This problem takes as input a graph and outputs a generating set for the automorphism group of that graph, with the generators specified as permutations on the vertex set of the graph. This reduces to the set stabilizer problem by viewing the permutation group of the vertex set as the group $G$ acting on the set of vertex pairs, and the set $S$ as the set of edges (viewed as a subset of the set of vertex pairs).