5
$\begingroup$

I'm looking for a way to measure how interconnected a graph is. It's well known that graphs can be broken down into connected components. It seems, though, that even in the cases where the graph is made of only one connected component, we can measure how interconnected that component is. Is it "almost" two components (if we would remove a small number of edges)? What is the correlation between edges (that is, if vertices A and B are each connected to C, is there a higher probability that A and B are themselves connected). I don't know how to define this measure properly, but I'm sure there are existing measures already defined.

It would seem to me that this would be a great way to measure the difficulty of an instance of the SAT problem. Representing variables as nodes and being in the same clause as edges, it would seem the difficulty of the problem is related to the interconnectedness of the graph.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
12
$\begingroup$

A standard measure of "interconnectedness" is how expanding the graph is. There are several ways to define expansion that are all related. The algebraic way is by measuring the second largest eigenvalue (in absolute value) of the adjacency matrix. The largest eigenvalue is a graph in which all vertices have degree D is always D. If the second largest eigenvalue is much smaller than D, then every two sets of vertices in the graph have roughly as many edges between them as if the edges were chosen at random (this is the expanding mixing lemma). For more info about graph expansion, see this course: http://www.math.ias.edu/~boaz/ExpanderCourse/

If the graph is an expander, the entire graph is one big, very interconnected, component. This is the case with random SAT instances that are believed to be hard (for the appropriate clauses ratio).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Very interesting, thanks. So, you're confirming my intuition: we can measure the "interconnectedness" as you describe, and that does predict that apparent hardness of the SAT problem. Yes? $\endgroup$
    – SRobertJames
    Commented Nov 7, 2010 at 16:01
  • 1
    $\begingroup$ I think that there is truth to the intuition that the "interconnectedness" of the clauses and variables graph goes hand in hand with the hardness of the instance, but all these intuitions are far from proved. Hastad's NP-hard instances for approximating 3SAT, for example, are not expanders, though they are obtained from expanders. The Unique Games Conjecture states that a problem that is inherently on non-expanders is extremely hard even to approximate. $\endgroup$
    – Dana Moshkovitz
    Commented Nov 7, 2010 at 16:31
5
$\begingroup$

A related question asks which problems are still NP-hard if your graph is a tree (i.e minimally connected). And there are many problems that are easy to solve on graphs of bounded treewidth. In fact, you can even solve #SAT in polynomial time on graphs of bounded treewidth

In general, notions of "interconnectedness" are so varied that I'm skeptical any single notion will be useful as a complexity demarcator.

Improve this answer
$\endgroup$
3
$\begingroup$

How about Connectivity?

Improve this answer
$\endgroup$
1
  • $\begingroup$ In fact lots of geometric information can often be extracted from connectivity information. For example, Steinitz's Theorem says that a graph is the vertex-edge graph of a 3-dimensional polytope if and only if the graph is planar and 3-connected. Furthermore, Balinski's Theorem says that the vertex-edge graph of a d-polytope must be d-connected. $\endgroup$
    – Joseph Malkevitch
    Commented Nov 7, 2010 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.