
Boost Users : 
Subject: Re: [Boostusers] [BGL] Separating twin vertices
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 20110318 22:37:05
On Fri, 18 Mar 2011, Shaun Jackman wrote:
> 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.
Somewhat.
> 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>
My understanding from the papers I've looked at is that no matter how you
set the variables in the strong backdoor set, the rest of the problem can
be decided quickly, and a weak backdoor is the same except that it's only
fast for one variable assignment. I don't think those are what you're
interested in, though, since you only have binary clauses now (and so the
problem is always fast to solve exactly). The problem you have (at least
according to the way you've described it) is the deletion renamable Horn
backdoor problem, where you delete variables from an arbitrary 2SAT
problem to find a satisfiable one. You're trying to find a backdoor set
of variables in a SAT problem that you don't have around (in the actual
backdoor problem, the 2SAT problem is derived from an arbitrary SAT
problem, and you have the 2SAT version already).
> 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?
No, but I haven't looked. I have thought of how to phrase your problem as
a weighted MAX2SAT problem (where you delete edges rather than vertices),
and there is software for that. One of the papers I sent you also has a
setpacking phrasing of the problem, and you might be able to find
software for that or use a more general integer linear
programming/pseudoBoolean programming solver for it. There is some
software for PBP at http://www.cril.univartois.fr/PB10/ and
http://minisat.se/downloads/MiniSat+.pdf. You can write your problem as
pseudoBoolean by creating variables "a" and "ignA" for each variable "a"
in your original 2SAT problem and writing each clause as a constraint:
a  b > a + b + ignA + ignB >= 1
~a  b > a + b + ignA + ignB >= 0
a  ~b > a  b + ignA + ignB >= 0
~a  ~b > a  b + ignA + ignB >= 1
and then minimizing the sum of the ign* variables; all variables here are
required to be either 0 or 1.
 Jeremiah Willcock
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