Boost Users :

Subject: Re: [Boost-users] [BGL] Separating twin vertices
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-03-17 21:55:48

On Thu, 17 Mar 2011, Shaun Jackman wrote:

> On Thu, 2010-08-12 at 22:18 -0700, Jeremiah Willcock wrote:
>> On Thu, 12 Aug 2010, Shaun Jackman wrote:
>>
>>> Hi,
>>>
>>> I have a directed graph where every vertex has a twin vertex. It is
>>> known ahead of time which pairs of vertices are twins. I want to remove
>>> as few vertices as possible from the graph such that no vertex and its
>>> twin is in the same connected component. Could someone suggest an
>>> appropriate algorithm?
>>
>> Connected component or strongly connected component? I'm assuming for a
>> directed graph that you mean SCC. When you remove a vertex, do you also
>> remove its twin? Is there a relationship between an edge from A -> B and
>> from twin(A) -> twin(B) (or twin(B) -> twin(A)), in the sense that those
>> edges would need to be removed in pairs? That would be implied by needing
>> to remove a vertex and its twin at the same time. Do you need to remove
>> entire vertices, or would removing just edges be OK? Also, do you need an
>> exact solution or would an approximation be acceptable if an exact
>> algorithm was too inefficient?
>
> Hi Jeremiah,
>
> Yes, strongly connected component.
> Yes, when you remove a vertex you must also remove its twin.
> An edge A -> B implies the existence of a twin edge twin(B) -> twin(A),
> and in removing an edge, you must also remove its twin.
> Entire vertices need to be removed (not just edges).
> An approximate solution would be sufficient.
>
> After some reading of Wikipedia, I found that my graph looks remarkably
> similar to an implication graph

>
> and my problem sounds remarkably similar to the 2-satisfiability problem

>
> So, armed with this new vocabulary, I'm looking to remove the fewest
> number of vertices (and their twins) from an implication graph that is
> not 2-satisfiable, to make a new graph that is 2-satisfiable.

I had somewhat suspected that you had a problem related to 2SAT. Look at