Ten algorithms for the Homogeneous Set Sandwich Problem

• Vinícius Gusmão Pereira de Sá UFRJ

Abstract

This thesis presents state-of-the-art results in two areas of increasing relevance over recent years: graph sandwich problems and randomized algorithms. Sandwich problems are generalizations of recognition problems where the input graph is provided with a set of optional edges. The Homogeneous Set Sandwich Problem, subject of this thesis, is one of the few polynomial-time sandwich problems known to date. Following the first two algorithms (not ours) published for it (one of which proved incorrect in [Sá 2003]), we introduce a series of eight faster algorithms, among deterministic and randomized ones. The text shows a comprehensive range of continuously refined techniques, culminating at the establishment of the problem’s currently accepted upper bound.

References

Cerioli, M. R., Everett, H., Figueiredo, C. M. H., and Klein, S. (1998). The homogeneous set sandwich problem. Inf. Proc. Letters, 67:31–35.

Dahlhaus, E., Gustedt, J., and McConnell, R. M. (2001). Efficient and practical algorithms for sequential modular decomposition. Journal of Algorithms, 41:360–387.

Dantas, S., Faria, L., and Figueiredo, C. M. H. (2004). On decision and optimization (k,l)-graph sandwich problems. Disc. Appl. Math., 143:155–165.

Golumbic, M. C., Kaplan, H., and Shamir, R. (1995). Graph sandwich problems. Journal of Algorithms, 19:449–473.

Golumbic, M. C. and Wassermann, A. (1998). Complexity and algorithms for graph and hypergraph sandwich problems. Graphs Combin., 14:223–239.

Habib, M., Lebhar, E., and Paul, C. (2003). A note on finding all homogeneous set sandwiches. Inf. Proc. Letters, 87:147–151.

Kaplan, H. and Shamir, R. (1999). Bounded degree interval sandwich problems. Algorithmica, 24:96–104.

Lovász, L. (1972). Normal hypergraphs and the perfect graph conjecture. Disc. Math., 2:253–267.

McConnell, R. M. and Spinrad, J. (1994). Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In Proc. of the 5th ACM-SIAM Symposium on Disc. Alg., pages 536–545.

Sá, V. G. P. (2003). O problema-sanduíche para conjuntos homogêneos em grafos. Master’s thesis, Univ. Federal do Rio de Janeiro.

Sá, V. G. P., Figueiredo, C. M. H. and Fonseca, G. D. (2003). A fast Monte Carlo algorithm for the Homogeneous Set Sandwich Problem. In Proc. of Mathematical Programming in Rio: a Conference in Honour of Nelson Maculan, pages 35–39.

Sá, V. G. P., Figueiredo, C. M. H., Fonseca, G. D., and Spinrad, J. (2004). Faster deterministic and randomized algorithms on the homogeneous set sandwich problem. In 3rd Workshop on Efficient and Experimental Algorithms, volume 3059 of Lecture Notes Comput. Sci., pages 243–252. Springer-Verlag.

Sá, V. G. P and Figueiredo, C. M. H. (2005). A note on the Homogeneous Set Sandwich Problem. Inf. Proc. Letters, 93:75–81.

Sá, V. G. P. (2006). Dez algoritmos para o Problema-Sanduíche do Conjunto Homogêneo. PhD thesis, Univ. Federal do Rio de Janeiro. URL: [link].

Sá, V. G. P., Fonseca, G. D., Figueiredo, C. M. H., and Spinrad, J. (2006a). Algorithms for the Homogeneous Set Sandwich Problem. Algorithmica, 46:149–180.

Sá, V. G. P, Bornstein, C. F. and Figueiredo, C. M. H. (2006b). The Pair Completion algorithm for the Homogeneous Set Sandwich Problem. Inf. Proc. Letters, 98:87–91.

Tang, S., Yeh, F., and Wang, Y. (2001). An efficient algorithm for solving the homogeneous set sandwich problem. Inf. Proc. Letters, 77:17–22.