Parameterized Complexity of Cliques and Independent Sets in Complementary Prism Graphs

• Priscila Camargo UFF
• Alan D. A. Carneiro UFF
• Uéverton S. Santos UFF

DOI: https://doi.org/10.5753/etc.2018.3166

Abstract

The complementary prism GG̅ arises from the disjoint union of the graph G and its complement G̅ by adding the edges of a perfect matching joining pairs of corresponding vertices of G and G̅. The classical problems of graph theory, clique and independent set were proved NP-complete when the input graph is a complemantary prism. In this work, we study the complexity of both problems in complementary prisms graphs from the parameterized complexity point of view. First, we prove that these problems have a kernel and therefore are Fixed-Parameter Tractable (FPT). Then, we show that both problems do not admit polynomial kernel.

References

Bondy, J. A. and Murty, U. S. R. (1976). Graph theory with applications, volume 290. Macmilan.

Cygan, M., Fomin, F. V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized algorithms, volume 3. Springer.

dos Santos, V. F. and dos Santos Souza, U. (2015). Uma introdução à complexidade parametrizada.

Duarte, M. A., Penso, L., Rautenbach, D., and dos Santos Souza, U. (2017). Complexity properties of complementary prisms. Journal of Combinatorial Optimization, 33(2):365–372.

Erdös, P. and Szekeres, G. (1935). A combinatorial problem in geometry. Compositio Mathematica, 2:463–470.

Haynes, T. W., Henning, M. A., Slater, P. J., and van der Merwe, L. C. (2007). The complementary product of two graphs. Bulletin of the Institute of Combinatorics and its Applications, 51:21–30.