Re: [Boost-users] [BGL] Separating twin vertices

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
> http://en.wikipedia.org/wiki/Implication_graph
>
> and my problem sounds remarkably similar to the 2-satisfiability problem
> http://en.wikipedia.org/wiki/2-satisfiability
>
> 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 
http://www-pr.informatik.uni-tuebingen.de/mitarbeiter/stephankottler/downloads/Kottler_RHornBackdoors_Talk.pdf 
(might need to use cache) and 
http://www.cril.univ-artois.fr/~sais/papers/ictai06.pdf for some 
heuristics for the problem you are trying to solve.  The kind of 
variable-removal-based variant of MAX-2SAT is the same as the problem of 
deleting variables to make a set of arbitrary clauses renamable Horn (see 
the slides for details).  It is NP-complete to solve exactly (see page 7 
of http://www.cs.cornell.edu/gomes/papers/backdoors-cp07-camera.pdf and 
all of http://repository.cmu.edu/tepper/210/).

-- Jeremiah Willcock