Una relazione è nello stato Eliminato

Una relazione è nello stato Eliminato

L'unico modo di cui sono consapevole per farlo funzionare è definire la relazione come una relazione identificativa. Sarebbe necessario introdurre la chiave esterna da Availability a User come chiave esterna nel tuo modello...

public int ID { get; set; }
public int UserID { get; set; }
public User User { get; set; }

...e rendilo parte della chiave primaria:

modelBuilder.Entity<Availability>()
    .HasKey(a => new { a.ID, a.UserID });

Puoi estendere la tua mappatura per includere questa chiave esterna (solo per essere espliciti, non è richiesta perché EF la riconoscerà per convenzione):

modelBuilder.Entity<Availability>()
    .HasRequired(a => a.User)
    .WithMany(u => u.Availability)
    .HasForeignKey(a => a.UserID);

(A proposito:devi configurare la relazione solo da un lato. Non è necessario avere entrambe queste mappature nella tua domanda.)

Ora puoi cancellare la collezione con user.Availability.Clear(); e il Availability le entità verranno eliminate dal database.