NF-Finder - F.A.Q.


General questions

  • how does NFFinder work?
  • It works in two steps:

    Step 1 : it computes a filtered list of subsets of the group, according to your selection of filters and parameters. Any member of this list is called a "candidate A". The size of a candidate A is denoted by omega.

    Step 2 : for every candidate A, it tries to find at least one subset B such that (A,B) is a near-factorization (if there is one, it outputs (A,B)).

    Selection of parameters

    Filters

  • what is the equipartition filter?
  • It is known that any near-factorization (A,B) must meet the cosets of some subgroups (those of exponent at most 4) in a particular way. The equipartition filter keeps the candidates A which satisfy this property. It is very fast to be applied and quite efficient, thus it is recommended to apply it.

    It is useless for groups whose order is not even or a multiple of 3.

  • what is the dispersion filter?
  • The dispersion filter is quite similar to the equipartition filter, but usually less efficient. You should use it for small values of omega (the size of A), that is 3,4 or 5.
  • what is the intersection filter?
  • This is a filter available only for cyclic groups: it is known that a circular partitionable graph with two maximum cliques sharing at least omega-3 vertices is not a counter-example to the circular partitionable graphs conjecture. The intersection filter should be applied only when looking for a counter-example of the circular partitionable graphs conjecture: it keeps candidates A such that the intersection of A with A+x has at most omega-4 vertices, for every non-zero x.
  • what is the automorphisms filter?
  • The automorphism filter computes the sublist of non-isomorphic candidates A. This is usefull as only non-isomorphic near-factorizations are usually of interest. This is a very strong filter but it is very time expensive to apply. It relies on the automorphism group of the group considered, which takes time to be computed by itself (to compute it, you need gap and to run the script preprocessin_with_gap (see section Options, below)).
  • what is the "cut of search space" for?
  • This is an option to let you try to find any near-factorizations in groups which would take far too much time to be check exhaustivly: it allows you to set the number of subsets A to try. Of course, by limiting the number of subsets A to try, you are likely to miss some/many solutions.

    Number of processes

  • is it useful to set the number of processes to a number greater than 1, on a single processor station?
  • If there is no load automatic repartition in your network (this is likely), it is not.

    Options

  • How can I look for near-computation in groups other than the one provided ?
  • You need first to install GAP. Please make a copy of the script gap.sh under the name gap, somewhere to your path. Then run the script preprocessing_with_gap, and provide the parameters you are asked for, that is the order of the group your interested in (the script will make the computations for every group of such order). It may take quite a long time.