Abstract A polynomial time approximation algorithm A for the problem of finding a maximal independent set for cubic planar graphs is presented. It is shown that MA > 6/7 in the case of cubic planar graphs and MA = 7/8 in the case of triangle free cubic planar graphs where MA is the worst‐case ratio of the size of the independent set found by A to the size of the maximum independent set for the graph input to A.

Relational database schemes can be partitioned into acyclic (tree) schemes and cyclic schemes. This partitioning also classifies the natural join queries into tree queries and cyclic queries. The problems of determining the minimum number of joins needed (i) to transform a cyclic scheme into an acyclic one, and (ii) to solve a cyclic query are shown [GS1 82, GS2 82] to be two different NP-complete problems. We consider a class of database schemes, called simple schemes. We show that the two problems above are equivalent but remain to be NP-complete when they are restricted to simple schemes. We give a polynomial time algorithm for both problems on simple schemes whose qual graphs are chordal. As a by-product, we also show that an edge contraction problem on undirected graphs is NP-complete and it is polynomial when the graph is chordal.