The well-covered partitioned probe split problem is polynomial

• S. R. Alves FAETEC/RJ
• F. Couto UFRRJ
• L. Faria UERJ
• S. Klein UFRJ
• U. dos S. Souza UFF

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

Abstract

A graph G = (V,E) is well-covered if each maximal independent set of G is maximum. A graph G = (V,E) is split if there is a partition V = (S,K), where S is an independent set and K is a clique. A well-covered split graph is at a same time well-covered and split. Given a class C of graphs, a graph G = (V,E) is C−probe if there is a partition for V = (N,P) into probes P and non-probes N, where N is an independent set and new edges may be added between non-probes such that the resulting graph is in the graph class C. We say that (N,P) is a C probe partition for G. The C−PARTITIONED PROBE problem consists of an input graph G and a probe partition V = (N,P) and the question: Is (N,P) a C−probe partition? In this paper we consider C the class of well-covered split graphs, and we prove that C−PARTITIONED PROBE problem belong to the polynomial problem class P.

References

Alves, S. R., Dabrowski, K. K., Faria, L., Klein, S., Sau, I., and Souza, U. S. (2016). On the (parameterized) complexity of recognizing well-covered (r, l)-graphs. In COCOA 2016, Hong Kong, China, 2016, pages 423 – 437. LNCS.

Chvátal, V. and Slater, P. J. (1993). A note on well-covered graphs. In John Gimbel, J. W. K. and Quintas, L. V., editors, Quo Vadis, Graph Theory?, volume 55 of Annals of Discrete Mathematics, pages 179 – 181. Elsevier.

Feder, T., Hell, P., Klein, S., and Motwani, R. (1999). Complexity of graph partition problems. In Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, STOC ’99, pages 464 – 472. ACM, New York, NY, USA.

Golumbic, M., Kaplan, H., and Shamir, R. (1995). Graph sandwich problems. volume 19, pages 449 – 473.

Golumbic, M. C. (1980). Algorithmic graph theory and perfect graphs. In Academic Press, volume 1, pages 149 – 156. Elsevier Science.