What is the best way to delete a relationship using the Web Serivce API?

I would like to delete a relationship between Contacts and a Custom module, I guess marking it as 'deleted' would be the way out.

It is a many-many relationship and makes use of a relationship table to store the relations.

Which method from the API should I use?
Is it possible to provide this functionality to both normal and Portal Only users?

Thanks,
~ Vikas