TR-2016-20

The complexity of the Clar number problem and an FPT algorithm

Erika Bérczi-Kovács, Attila Bernáth



Abstract

The Clar number of a (hydro)carbon molecule, introduced by Clar [E. 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 planar 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 [H.G. Abeledo and G.W. Atkinson, Unimodularity of the clar number problem, Linear algebra and its applications 420 (2007), no.2, 441-448] 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 NP-hard. We also prove 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 FPT algorithm that determines the Clar number of a given 2-connected plane graph. The parameter of the algorithm is the length of the shortest odd join in the planar dual graph. For fullerenes this is not yet a polynomial algorithm, but for certain carbon nanotubes it gives an efficient algorithm.


Bibtex entry:

@techreport{egres-16-20,
AUTHOR = {B{\'e}rczi-Kov{\'a}cs, Erika and Bern{\'a}th, Attila},
TITLE = {The complexity of the Clar number problem and an FPT algorithm},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2016},
NUMBER = {TR-2016-20}
}


Last modification: 5.12.2018. Please email your comments to Tamás Király!