Strictly speaking, the only way to cascade values like that is by using ON UPDATE CASCADE. To do that, the column "is_deleted" has to be part of a unique constraint.
That alone isn't too hard. If company.id is your primary key, then the pair of columns {id, is_deleted} will also be unique. A unique constraint on that pair of columns would allow you to cascade updates through a foreign key reference.
But that won't work in your case, because you need to allow referencing values to be different from the referenced values.
So in your case, I think you have three options.
- Triggers
- Stored procedures
- Application code
In all those cases, you need to pay attention to permissions (probably revoking delete permissions) and to cases that can avoid your code. For example, the dbms command-line interface and GUI interface can be used to get around constraints in application code and, depending on permissions, in stored procedures.