7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Boson Apr 9 '15 at 15:14
  • $\begingroup$ 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. $\endgroup$ – Joshua Grochow Apr 11 '15 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.