
Boost Users : 
Subject: Re: [Boostusers] [BGL] Separating twin vertices
From: Shaun Jackman (sjackman_at_[hidden])
Date: 20110318 21:01:28
On Thu, 20110317 at 18:55 0700, Jeremiah Willcock wrote:
> On Thu, 17 Mar 2011, Shaun Jackman wrote:
>
> > On Thu, 20100812 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 2satisfiability problem
> > http://en.wikipedia.org/wiki/2satisfiability
> >
> > 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 2satisfiable, to make a new graph that is 2satisfiable.
>
> I had somewhat suspected that you had a problem related to 2SAT. Look at
> http://wwwpr.informatik.unituebingen.de/mitarbeiter/stephankottler/downloads/Kottler_RHornBackdoors_Talk.pdf
> (might need to use cache) and
> http://www.cril.univartois.fr/~sais/papers/ictai06.pdf for some
> heuristics for the problem you are trying to solve. The kind of
> variableremovalbased variant of MAX2SAT 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 NPcomplete to solve exactly (see page 7
> of http://www.cs.cornell.edu/gomes/papers/backdoorscp07camera.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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net