This paper is the second in a series in which the authors study the conjugacy decision problem (CDP) and the conjugacy search problem (CSP) in Garside groups.

The ultra summit set __\( \mathrm{USS}(X) \)__ of an element __\( X \)__ in a Garside group __\( G \)__ is a finite set of elements in __\( G \)__, which is a complete invariant of the conjugacy class of __\( X \)__ in __\( G \)__. A fundamental question, if one wishes to find bounds on the size of __\( \mathrm{USS}(X) \)__, is to understand its structure. In this paper we introduce two new operations on elements __\( Y \in \mathrm{USS}(X) \)__, called ‘partial cycling’ and ‘partial twisted decycling’, and prove that if __\( Y \)__, __\( Z \in \mathrm{USS}(X) \)__, then __\( Y \)__ and __\( Z \)__ are related by sequences of partial cyclings and partial twisted decyclings. These operations are a concrete way to understand the minimal simple elements whose existence follows from the convexity property of ultra summit sets.

Using partial cycling and partial twisted decycling, we investigate the structure of a directed graph __\( \Gamma_X \)__ determined by __\( \mathrm{USS}(X) \)__, and show that __\( \Gamma_X \)__ can be decomposed into ‘black’ and ‘grey’ subgraphs. There are applications relating to the authors’ program for finding a polynomial solution to the CDP/CSP in the case of braids, which is outlined in the first paper of this series. A different application is to give a new algorithm for solving the CDP/CSP in Garside groups which is faster than all other known algorithms, even though its theoretical complexity is the same as that of the established algorithm using ultra summit sets. There are also applications to the theory of reductive groups.