<p>Many of the best results around graph isomorphism and permutation group algorithms are parametrized by some structure of a relevant group. For example, let $\mathcal{S}_d$ denote the class of groups all of whose composition factors are isomorphic to subgroups of $S_d$. Then coset intersection for groups in $\mathcal{S}_d$ can be solved in polynomial time for constant d. This is closely related to the polynomial-time isomorphism test for bounded-degree graphs. </p>

<p>I think there are also several other problems that are solvable in polynomial time when certain associated groups are in $\mathcal{S}_d$ for $d=O(1)$, but I don't have references off the top of my head.</p>

CC BY-SA 3.0
2015-04-09T15:14:03.317Z
I see your point, but the parameter would still be _d_, not the group itself.
In fact, I am rather curious about the possibility of reducing a W[_t_]-complete (for some _t_) problem to my problem: how would you map an integer parameter _k_ to a group parameter _G_?
Boson
CC BY-SA 3.0
2015-04-11T07:18:16.290Z
Indeed. Turning an integer parameter into a group is essentially asking for natural, infinite families of finite groups. Some examples: cyclic groups, dihedral groups, symmetric groups, alternating groups, $SL_k(F_q)$ (for fixed or varying q), or the other families of (almost) simple groups of Lie type.
Joshua Grochow
CC BY-SA 3.0
2015-04-08T18:28:41.317Z
2015-04-08T18:28:41.317Z
Joshua Grochow
<p>I am currently studying a complexity problem related to symmetries, and am considering a study of the parameterized complexity of the problem.</p>

<p>In theory, any part of the input can be fixed as a parameter, but in practice it seems like parameters are almost always integers.
Some problems use a graph as a parameter, such as the testing whether H is a minor of G (polynomial when H is fixed, hence fixed parameter tractable with H as a parameter).</p>

<p><strong>My question is</strong>: do you know any study of the complexity of a problem parameterized by a group?</p>

<p>Candidates could be classical group-related problems, such as coset intersection problem or hidden subgroup problem, but I have not found such parameterized complexity study for them.</p>

<parameterized-complexity><gr.group-theory>
Problem with a group as complexity parameter?
Boson
# Problem with a group as complexity parameter?

(Asked by: username_0 on 2015-04-08)

I am currently studying a complexity problem related to symmetries, and am considering a study of the parameterized complexity of the problem.

In theory, any part of the input can be fixed as a parameter, but in practice it seems like parameters are almost always integers.
Some problems use a graph as a parameter, such as the testing whether H is a minor of G (polynomial when H is fixed, hence fixed parameter tractable with H as a parameter).

**My question is**: do you know any study of the complexity of a problem parameterized by a group?

Candidates could be classical group-related problems, such as coset intersection problem or hidden subgroup problem, but I have not found such parameterized complexity study for them.

**Tags:** parameterized-complexity, gr.group-theory

---

## 1 answers

### Answer by username_1 on 2015-04-08. Score: 2

Many of the best results around graph isomorphism and permutation group algorithms are parametrized by some structure of a relevant group. For example, let $\mathcal{S}\_d$ denote the class of groups all of whose composition factors are isomorphic to subgroups of $S\_d$. Then coset intersection for groups in $\mathcal{S}\_d$ can be solved in polynomial time for constant d. This is closely related to the polynomial-time isomorphism test for bounded-degree graphs.

I think there are also several other problems that are solvable in polynomial time when certain associated groups are in $\mathcal{S}\_d$ for $d=O(1)$, but I don't have references off the top of my head.

> **Comments:**
> **username_0**: I see your point, but the parameter would still be _d_, not the group itself. In fact, I am rather curious about the possibility of reducing a W[_t_]-complete (for some _t_) problem to my problem: how would you map an integer parameter _k_ to a group parameter _G_?  
> **username_1**: Indeed. Turning an integer parameter into a group is essentially asking for natural, infinite families of finite groups. Some examples: cyclic groups, dihedral groups, symmetric groups, alternating groups, $SL_k(F_q)$ (for fixed or varying q), or the other families of (almost) simple groups of Lie type.  

---

