The inner parsec of the supermassive black hole (SMBH) in the center of the Milky Way, Sgr A★, contains a cluster of several hundred young, massive stars. Their complex, highly structured kinematics poses an intriguing conundrum on their origin within the strong tidal field close to the SMBH. It has been suggested that the encounter of a gas cloud with the SMBH could produce a fast rotating disk of coeval, massive stars. This result however differs strongly from the observed multi-component orbital distribution. We demonstrate that star-star scattering within the disk can only weakly change their orbits and cannot explain the observations, even if one includes the dispersal of an additional gaseous disk component. Including however the gravitational interaction with a putative intermediate-mass companion (IMC) of Sgr A$^\star$, possibly an intermediate mass black hole, naturally scatters the stars into their current kinematic configuration on timescales consistent with their stellar ages.