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/downloa... (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