Inspired by previous work of Diaz, Petit, Serna, and Trevisan (Approximating layout problems on random graphs, Discrete Mathematics, 235, 2001, 245-253), we show that several well-known graph layout problems are approximable to within a factor arbitrarily close to 1 of the optimal with high probability for random graphs drawn from an Erdös-Renyi distribution with appropriate sparsity conditions using only elementary probabilistic analysis. Moreover, we show that the same results hold for the analogous problems on directed acyclic graphs.
References
[1]
Díaz, J., Petit, J. and Serna, M. (2002) A Survey of Graph Layout Problems. ACM Computing Surveys, 34, 313-356. https://doi.org/10.1145/568522.568523
[2]
Lengauer, T. (1981) Black-White Pebbles and Graph Separation. Acta Informatica, 16, 465-475. https://doi.org/10.1007/BF00264496
[3]
Gavril, F. (2011) Some NP-Complete Problems on Graphs. 2011 45th Annual Conference on Information Sciences and Systems, Baltimore, MD, 23-25 March 2011.
[4]
Cheung, K., Girardet, P., Moatamed, A. and Ruiz, E. (2018) On a Directed Layout Problem. Manuscript in Preparation.
[5]
Brandes, U. and Fleischer, D. (2009) Vertex Bisection Is Hard, too. Journal of Graph Algorithms and Applications, 13, 119-131. https://doi.org/10.7155/jgaa.00179
[6]
Garey, M.R. and Johnson, D.S. (1979) Computers and Intractibility: A Guide to the Theory of NP Completeness. Freeman and Co., New York.
[7]
Díaz, J., Petit, J., Trevisan, L. and Serna, M. (2001) Approximating Layout Problems on Random Graphs. Discrete Mathematics, 235, 245-253.
https://doi.org/10.1016/S0012-365X(00)00278-8
[8]
Gilbert, E.N. (1959) Random Graphs. The Annals of Mathematical Statistics, 30, 1141-1144.
[9]
Barak, A.B. and Erdös, P. (1984) On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph. SIAM Journal on Algebraic Discrete Methods, 5, 508-514.
[10]
Hoeffding, W. (1963) Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58, 13-30.
https://doi.org/10.1080/01621459.1963.10500830
