Added another edit
I also thought that you might be orphaning the other side of the relationship; you're deleting the Category entity from the Product, but are you also removing the Product from that Category? Consider using WillCascadeOnDelete (Cascade Delete for One-to-Zero-or-One Relationship in Entity Framework (EF)) or, alternatively, try include the relationships in your queries.
_ctx.Products.Include(p => p.Categories).Where(...)
Please let us know how that goes for you.
So, judging by Lorenzo's response, I can see what he's trying to do. I've been bitten by this in the past, along with maybe a few other people.
Choose option 3 if you think you have a Cascade Delete problem (which is now not so much an option as a requirement...).
Since we don't know the schema of CategoriesPerProduct: our perpetrator, the main problem, as best as I can tell, is that you're placing the item from CategoriesPerProduct in an impossible condition where it requires a Category to exist, but the Category has essentially been turned to null.
Consequently, you have a few choices:
ctx.Entry(category).State = EntityState.Deleted)