๐ฎ
๐ฎ
The Ethereal
Equivalence between pathbreadth and strong pathbreadth
September 17, 2018 ยท The Ethereal ยท ๐ Discrete Applied Mathematics
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Guillaume Ducoffe, Arne Leitert
arXiv ID
1809.06041
Category
cs.CC: Computational Complexity
Cross-listed
cs.DS
Citations
1
Venue
Discrete Applied Mathematics
Last Checked
6 months ago
Abstract
We say that a given graph $G = (V, E)$ has \emph{pathbreadth} at most $ฯ$, denoted $\pb(G) \leq ฯ$, if there exists a Roberston and Seymour's path decomposition where every bag is contained in the $ฯ$-neighbourhood of some vertex. Similarly, we say that $G$ has \emph{strong pathbreadth} at most $ฯ$, denoted $\spb(G) \leq ฯ$, if there exists a Roberston and Seymour's path decomposition where every bag is the complete $ฯ$-neighbourhood of some vertex. It is straightforward that $\pb(G) \leq \spb(G)$ for any graph $G$. Inspired from a close conjecture in [Leitert and Dragan, COCOA'16], we prove in this note that $\spb(G) \leq 4 \cdot \pb(G)$.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Computational Complexity
๐ฎ
๐ฎ
The Ethereal
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
๐ฎ
๐ฎ
The Ethereal
The Parallelism Tradeoff: Limitations of Log-Precision Transformers
๐ฎ
๐ฎ
The Ethereal
The Hardness of Approximation of Euclidean k-means
๐ฎ
๐ฎ
The Ethereal
Slightly Superexponential Parameterized Problems
๐ฎ
๐ฎ
The Ethereal