Efficient Algorithms for Optimization and
Enumeration Problems on Patchable Graphs
 
J.A. Makowsky

Abstract   :
 Graphs which occur as artefacts (VLSI, networks)  created by humans are
built stepwise (patched together) from simpler graphs and the history of
this building process (patch tree) is usually known.  Furthermore, the
amount of information needed to do the patching is usually very small
compared to the size of the graph.  We shall introduce a way of measuring
this information and call it the patch width pw(G) of a graph.
 
We shall exhibit a class of such patching operations which allows us to
use the patching history to make various decision, optimizitation and
enumerations problems solvable in time f(k)O(n), where n is the size of
the graph, and f(k) depends only on the patch width pw(G)=k, although
these problems are NP-hard (#P hard) in general. Examples of small patch
width are obtained in the case of graphs of tree width k, graphs of clique
width k, P_4 sparse graphs, and other classes previously studied in the
literature.  We shall illustrate this method for solving SAT, #SAT, HAM
and #HAM.  Our method works for problems definable in Monadic Second Order
Logic and uses a logical version of the Myhill-Nerode Theorem, the
Feferman-Vaught Theorem, adapted to graphs.  (Joint work with B. Courcelle
and U. Rotics)


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Prof. J.A.  Makowsky                    
e-mail: janos@cs.technion.ac.il
Preprints and additional information available via WWW:
        http://www.cs.technion.ac.il/~janos
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%