The complexity of the Clar number problem and an exact algorithm.

The Clar number of a (hydro)carbon molecule, introduced by Clar (The aromatic sextet, 1972), is the maximum number of mutually disjoint resonant hexagons in the molecule. Calculating the Clar number can be formulated as an optimization problem on 2-connected plane graphs. Namely, it is the maximum number of mutually disjoint even faces a perfect matching can simultaneously alternate on. It was proved by Abeledo and Atkinson (Linear Algebra Appl 420(2):441-448, 2007) that the Clar number can be computed in polynomial time if the plane graph has even faces only. We prove that calculating the Clar number in general 2-connected plane graphs is $$\mathsf {NP}$$ -hard. We also prove $$\mathsf {NP}$$ -hardness of the maximum independent set problem for 2-connected plane graphs with odd faces only, which may be of independent interest. Finally, we give an exact algorithm that determines the Clar number of a given 2-connected plane graph. The algorithm has a polynomial running time if the length of the shortest odd join in the planar dual graph is fixed, which gives an efficient algorithm for some fullerene classes, such as carbon nanotubes. [ABSTRACT FROM AUTHOR]