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

Subject: Re: [Boost-users] [BGL] Separating twin vertices
From: Shaun Jackman (sjackman_at_[hidden])
Date: 2011-03-18 21:01:28

On Thu, 2011-03-17 at 18:55 -0700, Jeremiah Willcock wrote:
> 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/).

Hi Jeremiah,

You seem to have some familiarity with my problem. Is the `Strong
Backdoor set' a set of variables that can be assigned a value without
contradicting any of the implication edges of the graph? Are the
remaining vertices then the ones that I want to remove from the graph?
The term `Strong Backdoor set' doesn't turn up in Wikipedia. That
usually means that I'm beyond my mathematical depth. <grin>

Do you know whether any of these papers have software that can be
downloaded and, if I'm lucky, read a graph formatted as a GraphViz dot
file?

Cheers,
Shaun