Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints

The 3-Hitting Set problem involves a family of subsets F of size at most three over an universe U. The goal is to find a subset of U of the smallest possible size that intersects every set in F. The version of the problem with parity constraints asks for a subset S of size at most k that, in addition to being a hitting set, also satisfies certain parity constraints on the sizes of the intersections of S with each set in the family F. In particular, an odd (even) set is a hitting set that hits every set at either one or three (two) elements, and a perfect code is a hitting set that intersects every set at exactly one element. These questions are of fundamental interest in many contexts for general set systems. Just as for Hitting Set, we find these questions to be interesting for the case of families consisting of sets of size at most three. In this work, we initiate an algorithmic study of these problems in this special case, focusing on a parameterized analysis. We show, for each problem, efficient fixed-parameter tractable algorithms using search trees that are tailor-made to the constraints in question, and also polynomial kernels using sunflower-like arguments in a manner that accounts for equivalence under the additional parity constraints.

Prediction of electronically nonadiabatic decomposition mechanisms of isolated gas phase nitrogen-rich energetic salt: Guanidium-triazolate

Electronically nonadiabatic decomposition pathways of guanidium triazolate are explored theoretically. Nonadiabatically coupled potential energy surfaces are explored at the complete active space self-consistent field (CASSCF) level of theory. For better estimation of energies complete active space second order perturbation theories (CASPT2 and CASMP2) are also employed. Density functional theory (DFT) with B3LYP functional and MP2 level of theory are used to explore subsequent ground state decomposition pathways. In comparison with all possible stable decomposition products (such as, N-2, NH3, HNC, HCN, NH2CN and CH3NC), only NH3 (with NH2CN) and N-2 are predicted to be energetically most accessible initial decomposition products. Furthermore, different conical intersections between the S-1 and S-0 surfaces, which are computed at the CASSCF(14,10)/6-31G(d) level of theory, are found to play an essential role in the excited state deactivation process of guanidium triazolate. This is the first report on the electronically nonadiabatic decomposition mechanisms of isolated guanidium triazolate salt. (C) 2015 Elsevier B.V. All rights reserved.