×

The vertex separation number of a graph equals its path-width. (English) Zbl 0764.68121

Summary: We show that the problem of finding a graph’s vertex separation number and path-width are the same. The equivalence of these problems with the gate matrix layout and the node search number problems then follows immediately from the results of M. R. Fellows and M. A. Langston and M. Kirousis and C. H. Papadimitriou, respectively. The fixed parameter variants of problems are known to possess \(O(n^ 2)\) decision algorithms based on finite but unknown obstruction sets. We show how all tree obstructions in these sets may be constructively obtained.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
68R05 Combinatorics in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bryant, R. L.; Fellows, M. R.; Kinnersley, N. G.; Langston, M. A., On finding obstruction sets and polynomialtime algorithms for gate matrix layout, Proc. 25th Allerton Conf. on Communication, Control, and Computing, 397-398 (1987)
[2] Deo, N.; Krishnamoorthy, M. S.; Langston, M. A., Exact and approximate solutions for the gate matrix layout problem, IEEE Trans. Computer-Aided Design, 6, 79-84 (1987)
[3] Ellis, J. A.; Sudborough, I. H.; Turner, J. S., Graph separation and search number, (Tech. Rept. DCS-66-IR (1987), Dept. of Computer Science, University of Victoria) · Zbl 0942.68641
[4] Fellows, M. R.; Langston, M. A., Nonconstructive advances in polynomial-time complexity, Inform. Process. Lett., 26, 157-162 (1987) · Zbl 0637.68053
[5] Fellows, M. R.; Langston, M. A., Nonconstructive tools for proving polynomial-time decidability, J. ACM, 35, 727-739 (1988) · Zbl 0652.68049
[6] Fellows, M. R.; Langston, M. A., On search, decision and the efficiency of polynomial-time algorithms, Proc. 21st ACM Symp. on the Theory of Computing, 501-512 (1989)
[7] Kinnersley, N. G., Obstruction set isolation for layout permutation problems, (Ph.D. Thesis (1989), Washington State University)
[8] Kirousis, M.; Papadimitriou, C. H., Interval graphs and searching, Discrete Math., 55, 181-184 (1985) · Zbl 0566.05056
[9] Kirousis, M.; Papadimitriou, C. H., Searching and pebbling, Theoret. Comput. Sci., 47, 205-218 (1986) · Zbl 0616.68064
[10] LaPaugh, A., Recontamination does not help to search a graph, (Tech. Rept. (1983), Electrical Engineering and Computer Science Dept., Princeton University) · Zbl 0768.68048
[11] Lengauer, T., Black-White Pebbles and Graph Separation, Acta Inform., 16, 465-475 (1981) · Zbl 0454.68027
[12] Parsons, T. D., Pursuit-evasion in a graph, (Alavi, Y.; Lick, D. R., Theory and Application of Graphs (1976), Springer: Springer Berlin), 426-441 · Zbl 0379.05026
[13] Robertson, N.; Seymour, P. D., Disjoint paths - A survey, SIAM J. Algebraic Discrete Methods, 6, 300-305 (1985) · Zbl 0565.05045
[14] Robertson, N.; Seymour, P. D., Graph minors - A survey, (Anderson, I., Surveys in Combinatorics (1985), Cambridge University Press: Cambridge University Press Cambridge), 153-171 · Zbl 0764.05069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.