Published 2018 | Version v1
Journal article

A short note on the complexity of computing strong pathbreadth

Contributors

Other:

Description

The strong pathbreadth of a given graph G is the minimum ρ such that G admits a Robertson and Seymour's path decomposition where every bag is the complete ρ-neighbourhood of some vertex in G. We prove that deciding whether a given graph has strong pathbreadth at most one is NP-complete. The latter answers negatively to a conjecture of [Leitert and Dragan, CO-COA'16].

Abstract

International audience

Additional details

Identifiers

URL
https://hal.science/hal-01735826
URN
urn:oai:HAL:hal-01735826v1

Origin repository

Origin repository
UNICA