Why is this delete operation slower after a foreign key relationship has been added?
It's the check if the owner is still referenced by the cats table during the DELETE. The check is essentially done using a select * from cats where owner_id = ? for every owner that you delete. 

You can speed up the check by creating an index on the foreign key column:

create index on cats (owner_id);