This problem is precisely equivalent to the Vertex Cover problem on a bipartite graph, with a vertex on one side for each first-name initial, and a vertex on the other side for each last-name initial. Each person is an edge from the "first name" vertex to the "second name" vertex.

While vertex cover is NP-hard in general, it turns out to be polynomially solvable on a bipartite graph. Konig's theorem says the minimal vertex cover size is equal to the maximum matching size (and the matching can be found by standard max flow).

However, this problem is also solvable by enumeration. If we correctly guess the set of last-name initials that groups are formed around, then it is clear how many first-name groups are needed to complete the partition (by looking at the first names for all people whose last initial was not chosen). There are 2^18 = 262,144 choices for the last-name groups, so we can afford to try them all.

• Year 1.
  Answer: 3
  This can be achieved using first initials (JS) and last initials (C)
  This is required because of following incompatible people: EC JP SG

• Year 2.
  Answer: 6
  This can be achieved using first initials (DEJMRT) and last initials ()
  This is required because of following incompatible people: DK ED JB MM RF TH

• Year 3.
  Answer: 18
  This can be achieved using first initials (GHIJKLMNOPQRSTUVWX) and last initials ()
  This is required because of following incompatible people: GA HB IC JD KE LF MG NH OI PJ QK RL SM TN UO VP WQ XR

• Year 4.
  Answer: 1
  This can be achieved using first initials (A) and last initials ()
  This is required because of following incompatible people: AA

• Year 5.
  Answer: 1
  This can be achieved using first initials (Z) and last initials ()
  This is required because of following incompatible people: ZR

• Year 6.
  Answer: 1
  This can be achieved using first initials (A) and last initials ()
  This is required because of following incompatible people: AR

• Year 7.
  Answer: 1
  This can be achieved using first initials (Z) and last initials ()
  This is required because of following incompatible people: ZA

• Year 8.
  Answer: 1
  This can be achieved using first initials (A) and last initials ()
  This is required because of following incompatible people: AA

• Year 9.
  Answer: 1
  This can be achieved using first initials () and last initials (R)
  This is required because of following incompatible people: AR

• Year 10.
  Answer: 5
  This can be achieved using first initials () and last initials (BCDEF)
  This is required because of following incompatible people: AF BB CC DD EE

• Year 11.
  Answer: 5
  This can be achieved using first initials (BCDEF) and last initials ()
  This is required because of following incompatible people: BB CC DD EE FA

• Year 12.
  Answer: 5
  This can be achieved using first initials (BCDEF) and last initials ()
  This is required because of following incompatible people: BB CC DD EE FA

• Year 13.
  Answer: 10
  This can be achieved using first initials (GHIJK) and last initials (BCDEF)
  This is required because of following incompatible people: AF BB CC DD EE GH HI IJ JK KG

• Year 14.
  Answer: 10
  This can be achieved using first initials () and last initials (ABCDEFGHIJ)
  This is required because of following incompatible people: AB BA CD DC EF FE GH HG IJ JI

• Year 15.
  Answer: 10
  This can be achieved using first initials (ABCDEFGHIJ) and last initials ()
  This is required because of following incompatible people: AB BA CD DC EF FE GH HG IJ JI

• Year 16.
  Answer: 14
  This can be achieved using first initials (ABDJYZ) and last initials (BEGIKLOP)
  This is required because of following incompatible people: AF BN CP DA EE FL HO IG JC KI MK NB YH ZD

• Year 17.
  Answer: 15
  This can be achieved using first initials (GIKLTXYZ) and last initials (DGIKNOP)
  This is required because of following incompatible people: AN BP CG DO EI FK GL IB JD KE LJ TF XC YH ZA

• Year 18.
  Answer: 16
  This can be achieved using first initials (CDMORXY) and last initials (ABCFHIJLN)
  This is required because of following incompatible people: AF BC CD DP EL FH GN HI JJ KB LA MO OM RK XG YE

• Year 19.
  Answer: 17
  This can be achieved using first initials (ADELORWXZ) and last initials (ACDFIMNR)
  This is required because of following incompatible people: AL BR CN DK EP FC GM HI IF JD KA LO OG RB WJ XH ZE