Boost logo

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
(might need to use cache) and 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 and
all of

-- Jeremiah Willcock

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at