Sandwich and probe problems for excluding paths
Abstract
Let Pk denote an induced path on k vertices. For k ≥ 5, we show that the Pk-free sandwich problem, partitioned probe problem, and unpartitioned probe problem are NP-complete. For k ≤ 4, it is known that the Pk-free sandwich problem, partitioned probe problem, and unpartitioned probe problem are in P.
Collections
Cite this version of the work
Celina Miraglia Herrera de Figueiredo, Sophie Spirkl
(2018).
Sandwich and probe problems for excluding paths. UWSpace.
http://hdl.handle.net/10012/18596
Other formats
The following license files are associated with this item:
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivatives 4.0 International
Related items
Showing items related by title, author, creator and subject.
-
Radiotherapy Cancer Treatment: Investigating Real-Time Position and Dose Control, the Sensor-Delayed Plant Output Estimation Problem, and the Nonovershooting Step Response Problem
Stewart, James (University of Waterloo, 2006-12-18)For over a century, physicians have prescribed x-ray radiation to destroy or impede the growth of cancerous tumours. Modern radiation therapy machines shape the radiation beam to balance the competing goals of maximizing ... -
The Frobenius Problem in a Free Monoid
Xu, Zhi (University of Waterloo, 2009-08-21)Given positive integers c1,c2,...,ck with gcd(c1,c2,...,ck) = 1, the Frobenius problem (FP) is to compute the largest integer g(c1,c2,...,ck) that cannot be written as a non-negative integer linear combination of c1,c2,...,ck. ... -
Eigenvalue, Quadratic Programming and Semidefinite Programming Bounds for Graph Partitioning Problems
Wang, Ningchuan (University of Waterloo, 2014-09-03)The Graph Partitioning problems are hard combinatorial optimization problems. We are interested in both lower bounds and upper bounds. We introduce several methods including basic eigenvalue and projected eigenvalue ...