4-COLORABILITY

I have given a short review of algorithms for 5-COLORING of planar graph. The best known algorithm is linear in the number of vertices
What is about 4-COLORING of planar graph. We know that each planar graph is 4-COLORABLE is it easy to find 4-COLORING.
Yes.
The polynomial, namely n^4 algorithm was given by K. Appel, W. Haken in 1989. K. Appel, W. Haken, "Every planar map is four colorable", Contemp. Math. 98, 1-741
The algorithm is based on their original proof.
Then their result was improved by Robertson, Sanders, Seymour, Thomas in STOC-96 paper "Efficiently four-coloring planar graphs" and this algorithm has a quadratic complexity.

What is interesting that a problem of 4-COLORING is NP-hard for a 3-colorable graph (meaning given a graph G, which is known to be 3-COLORABLE, find 4-COLORING of it)
This result was prooved in 1993 by Khanna, Linial, Safra, "On the hardness of approximating the chromatic number", 2nd Israel Symposium on Theory and Computing Systems (ISTCS). Their proof uses PCP theorem. Their result immediately generalize to NP-hardness of k + 2 floor(k/3)-1 coloring of k-colorable graphs.
In 2000 Guruswami and Khanna in their paper presented at IEEE CCC gave a nice proof of NP-hardness of 4-COLORABILITY without use of the PCP theorem. Actually they proved even stronger result: 4-COLORING is NP-hard for degree-bounded 3-COLORABLE graph

Another, interesting result about coloring (not just 4-coloring). There does not exist a polynomial algorithm which approximates coloring problem with the factor better then n^\epsilon, for some \epsilon. Very easy to comprehend explanation of the proof (as well many other approximation-hard results) is in excellent a bok chapter about PCP theorem written by Stefan Hougardy

Carnevale di Venezia, yesterday

carna-2006 - 20.JPG
Originally uploaded by alopatenko.

See SELECTED PHOTOS

Logic and Databases workshop on Cambridge

Next week
An Isaac Newton Institute Workshop
Logic and Databases

Prof. Bertossi is going to present results we obtained last Summer during his visit to Bolzano.

The Graph Coloring Problem

The problem: given a planar graph G and the number k, color G (means find a map V -> C, where V is a set of vertices of G, C is a set of k colors), such that no two adjacent vertices have the same color.
It is well-known that 3-coloring for planar graph is NP-complete.
Lipton and Miller (Information Processing Letter, 1978, v. 7, 4, "A batching method for coloring planar graphs") proved that 5-graph coloring is in O(n log n). They improved the result of D. Johnson, O(n^2) algorithm for 5-coloring (D. Johnson, Worst case behaviour of graph algorithm, 1974). After their result was impoved by Chiba, Nishizeki, Saito (A linear-time algorithm for five-coloring a planar graph, LNCS 108, 1981). Joseph Naor discovered that five coloring is in NC , or it can solved in polylogarithmic time on the machine with polynomial number of processors (to be more exact in O(log^5) time on O(n^3) processors)

The result is presented at J. Naor, A Fast Parallel Coloring Of Planar Graphs With Five Colors, Information Processing Letters 25(1987), 51-53

Herein the outline of the algorithm

Subroutine MAXINDSET: computing the maximal independent set of a planar graph: known to be in NC (log^2 time on n^3: Luby, A simple parallel coloring for the maximal independent set, SICOMP 15(4), 1986)

Algorithm is based on the recursion
COLORING
1 delete a set of independent vertices whose size is at least a fixed fraction A of the graph
2 apply COLORING to the remaining graph
3 extend the obtained coloring to the deleted vertices

since A is fixed, then the number of runs is logarithmic.
MAXINDSET is in NC, as well the set of deleted vertices is in NC
Extending the coloring is in NC

The Result is based on two simple lemmas
Lemma: More then 1/6 n vertices have degree less then 7
Proof: Suppose that the number of vertices with degree less then 7 is more then 1/6 n.
In that case the sum of degrees is more then 6n.
but it is known that the sum of the degrees in the planar graph is at most 6n-12

Lemma: Let U be a set of vertices whose degree is less then 7. The size of every maximal independent set in U[G] (induced subgraph defined by G) is at least 1/7|U|
Proof: obv.

So, the five coloring algorithm
COLORING

1 find a maximal independent set I in the induced subgraph defined by the vertices of degree less then 7
2 delete I from the graph G' = G \ I, apply COL = COLORING(G')
3 extend 5 coloring from G' to G
for each v in I
a the number of neighbours of v is less then 5, then color v; continue
b Let a and b be a pair of colors which as chosen by at least 1/10 of


TO BE COMLETED

the database connection pooling

Just to summarize and add a few words to This discussion (a link to the thread at The Design of Software)


Whenever one implements a 3-tier application, the database connection pooling must be used.
Exceptions:

1. light-weight applications
2. application with security policy implemented at the database side: if each application user has to log in to the database under his database account a) so the security restrictions of data access can be applied b) to audit his actions
3. database security capabilities are used to identify and authorise user

Database connection pooling is supported by most database connectivity API

It is supported by

1. JDBC starting from JDBC 2.0 (see a tutorial on JDBC connection pooling by Sun or an Oracle Magazine article ) so Java program can use it
2. ODBC starting from ODBC 3.0 (see Microsoft's FAQ about connection pooling for ODBC), so C++, MS Visual Basic etc application can use it
3. proprietary database connection APIs like Oracle Call Interface (OCI) see OCI Programmer Guide, Ch. 9 C++, C
   

Reasons:

1. the creation of a database connection takes some time (not short, up to 1 second to Oracle DBMS), so if users frequently connect/disconnect to the database, then connection pooling must be used. A good example would be an internet shop, such that many users connected annd disconnect it . From my experience I would 10 connections per second is a limit for non-pooled database access.
2. each database connection gets some memory at both client and server side to handle it. Even worse, if you run your Oracle in dedicated server mode, then each client has its own server process. It is not good at all if you do not run long-running queries, a batch job or some administrative task like using RMAN to restore/back up a database.
   
3. so, performance certanly degradated if you use one connection per user see some experiments JDBC Connection Pooling Best Practises
4. database vendor may charge you per connection or the number of connections may be restricted by some DBA policy .
   

Problems:

1. you have to implement proper multi-threading at the 2nd layer, see examples at the tutorial above how to do it
   
2. some database engines or server configurations may restrict the number of database locks per connection
3. performance may decrease if there are too many users so there are no enough connection in the pool to handle them. Just increase the number of connections. When the number of user decrease, decrease the number of connections. If your application is dynamic ... like internet-shop and the number of users very singificantly in time then creation and deletion of connection in the pool may degrate performance. you need some techniques based on queuu theory to forecast the number of connections.
   

test data

If you need a large database for experiments or a demonstration,
that I would recommend to use the IMDB database (http://www.imdb.com/interfaces#plain)
It contains around 30 tables, some of them contain around 2M entries.
There are foreign keys, keys.
The database is a set of plain text files, but it took 2 hours of my time to write perl script which convert it to Oracle SQL*Loader dump file.
The only problem is that you can not use this database for online demonstrations since data are copyrighted by IMDB.

structural equivalence of boolean functions and the graph isomorphism problem

One of the important problems for synthesis and verification of Boolean circuits is:
if two Boolean functions are equivalent.

Two booleans functions of the same arity are equivalent if they map the same values into the same values.
It is well known that this formula is NP-complete in respect to the size of the Boolean function representation.

Consider another problem STRUCTURAL EQUIVALENCE of BOOLEAN FUNCTIONS:
given the representation of two Boolean functions as propositional formulae \Psi_1 and \Psi_2: is there exist a mapping from from variables \Psi_1 to variables of \Psi_2 with transposing o 1nd 1 states at any lead such that the formalue will be syntactically equivalent.

Or two Boolean function representations are on the same orbit of the group generated by permutation and complementations of the variables

Basicaly it means:
given two circuit descriptions, do they represent the same physically circuit?

The complexity of this problem is not known, it is know that this problem is equivalent to the GI Graph Isomorphism problem.


Babai Luks algorithm for GI runs in O(c^n^{1/2})
For graphs of genus \leq g, the GI can be solved in O(n^{O(g)})
It is known (as a consequence of Bodlaender theorem), that for graphs with a bounded tree-width GI can be solved in polynomial time.


Let Aug(G) denote the automorphism group of G
The following problems are PTIME equivalent

1. Graph Isomorphism
2. Graph Isomorphism Counting (the number of isomorphism from G to H)
3. Complement Isomorphism: If G is isomorphic to its compliment
4. Generating Set for Aut(g): determine a generating set for Aut(G)
5. context-free grammar isomorphism
6. conjuctive-query isomorphism
   

There is an evidence that GI is not NP-hard. Bopanna, HAstad, Zachos has shown (1982) that if the GI is N P-hard then polynomial hierarchy collapes to \Pi^p_2

minimum storage representation

this post is about the well-known graph-theoretic problem "Minimum Storage Representation"
Given a graph (V,E) determine a minimal graph (V, E*) such that there is a (directed) path from i to j in G iff there is a (directed) path from i to j in G*.
Basically, we have to find a minimum storage representation of the graph, which still allows us to answer reachability queries. Of course, there is a certain trade-off between minimum query time and minimum storage representation, but we do not care about it now.
In case if we impose a restriction that E* \subseteq E then the problem is named as Minimum Equivalent Graph (MEG) if a graph is undirected or Minimum Equivalent Digraph (MED) if graph is directed. MED has the number GT33 in Garey, Johnson
It is well-known that a decission version of the MEG(MED) problem (given graph G and the number k, if there exist a representation of the size \leq k) is NP-complete. By reduction of Directed Hamiltionian Circuit.
What happens in case if we relax a restriction that E* \subset E? In that case the problem is named a transitive reduction of G. For each acyclic graphs MEG = transitive reduction and for each acyclic graph there exists only one MEG.
Aho, Garey and Ullman (Aho Garey Ullman The transitive reduction of a directed graph, SIAM. J. Computing, 1(1972)) have shown that transitive reduction of each graph can be computed in polynomial time (in O(|V||E|))
GRAPH ENCODABILITY Given directed graphs (V,A) and (V',A') is the an encoding of the first graph into the second one: a one to one function V->V', such tht for each edge \in A, there exists a dirfected path in A'
This problem is solvable in PTIME for undirected graphs. The problem is solvable for directed graphs in PTIME if the first graph (which must be encoded) is fixed. In general case, the problem is NP-hard for for directed graphs. In case if egdes are weighted then even undirected version of the problem is NP-hard (A. Rosenberg, Data Encoding and Their Costs, Acta Informatica 1978, referenced by Johnson, The NP-completeness column, J. of Algorithms, 1982)

how hard is it

One of the branches of the algorithmic graph theory is a set of problems alike what is the minimum nuber of probes of the adjacency matrix of the graph is required in the worst case, in order to determine whether the graph posseses a given property P.
Of course, the only nontrivial properties are considered.
The upper limit of the probes is the size of adjacency matrix (n(n-1)/2) since the upper diagonal is necessary only.
Bollobas and Eldridge proved that for all nontrivial graph properties the minimum number of probes is \geq 2n-4, linear in the number of vertices of the graph.
A good example of the linear property is existence of a sink node (a node with in-degree=n-1 and out-degree=0) in a directed graph (loop-free).
Smith-Thomas proved that the existence of the sink is in 3n-log n - 3

An elusive property P (evasive property) is a property such that all essential entries of the adjacency matrix must be probed to establish P
Among evasive properties are: beeing a tree, beeing connected, beeing biconnected, beeing planar, beeing k-chromatic

What is a difference between existence of a sink and beeing connected?
Rivest and Vuillemin proved that for every nontrivial, monotone property of graphs, the minimum number of probes is \geq n^2/16
The conjecture that monotone properties are "hard" (evasive) is known as the Aanderaa-Rosenberg conjecture.
Kahn improved Rivest and Vuilemenn result up to n^2/4 for undirected graphs and King improved it to n^2/2 for directed graphs.

See

1. L. Lovasz and N. Young , Lecture Notes on Evasiveness of Graph Properties
2. Graph Algorithms by J. van Leeuwen in Handbook of Theoretical Computer Science, vol. A
   

lovely things

I like beautiful reductions in the complexity theory.
Reduction technique looks like a particular kind of programing.
Programming: given a language L (Python, C++, Scheme), and a problem P (input of census information, train scheduling, web information retrieval), you have to produce a program P in L, which solves P.
CT Given a (often very simple) "programming language" L: Clique problem over graphs, Algebraic equations over GF[2], Finite State Automaton Non-Equivalence, a problem P (which is usually has much more involved definition then language L) , you have to produce a reduction R of P to L.

Many beatiful reduction are given in the following articles:

1. Some Simplified NP-Complete Graph Problems, M. R. Garey, D. S. Johnson and L. Stockmeyer, Theoretical Comp. Sci., 1 (1976), 237-267.
2. T.J. Schäfer, Complexity of some two-person perfect-information games,
   J.Comput. Syst. Science, 16 (1978) 185--225.

A few days ago Fortnow reminded about very beautiful results on alternating TM

Scripting for Mobile Phones

Astonishing!
Python is ported to Symbion OS
See Matt Croydon's Res. Guide
There are a few ports of Python to Symbion: Nokia's, Pys60,
In particular, the Nokia's port includes

1. Camera, Calendar, Telephone API
2. Access to disk space and free memory
3. GPRS, BlueTooth
4. SMS
5. GUI widgets, scalable UI

and many other features

Wrappers for Google and Amazon sites, as well many other applications are available

Bill Gasarsh posted a list of the surpursing results in the theory:
http://weblog.fortnow.com/2005/12/surprising-results.html

Which are my 10 favorite ones?

1. Matrix Multiplication in O(n^2.87) time (less than n³ !!) (Strassen 1969).
2. Equivalence problem for Regular Expressions with Squaring is EXP-SPACE complete (Meyer, Stockmeyer FOCS72). A `natural' problem proven to NOT be in P!
3. P vs NP cannot be solved by techniques that relatives (Baker, Gill, Solovay 1975).
   
4. Permanent is #P comple
5. Shortest Path problem on planar graphs BETTER THAN O(n log n) (Fredersickson, 1983, FOCS).te. (Valiant 1979)
6. Bit commitment⇒SAT in Zero Knowledge (Brassard,Crepeau FOCS86, Goldreich,Micali,Wigderson CRYPTO86, JACM91)
   
7. Fixed Parameter Tractability material
8. PH in P^#P. (Toda FOCS89, SICOMP91)
9. Connection between PCP and Approximation
10. Grover's Quantum O(n^0.5) search algorithm (STOC 1996, Phy Review Letters 1997