The vertex separation number of a graph equals its path-width.

*(English)*Zbl 0764.68121Summary: 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 |

##### Keywords:

computational complexity; graph’s vertex separation number; path-width; decision algorithms; tree obstructions
PDF
BibTeX
XML
Cite

\textit{N. G. Kinnersley}, Inf. Process. Lett. 42, No. 6, 345--350 (1992; Zbl 0764.68121)

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, () · 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, () |

[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, () · 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, (), 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, (), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.