Computing the zig-zag number of directed graphs

The notion of zig-zag number was introduced as an attempt to provide a unified algorithmic framework for directed graphs. Nevertheless, little was known about the complexity of computing this directed graph invariant. We prove that deciding whether a directed graph has zig-zag number at most k is in...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2022-05, Vol.312, p.86-105
Main Authors: Dourado, Mitre C., de Figueiredo, Celina M.H., de Melo, Alexsander A., de Oliveira Oliveira, Mateus, Souza, Uéverton S.
Format: Article
Language:English
Subjects:
[formula omitted]-completeness
Computation
Computational complexity
Directed graphs
Directed width measure
Graph theory
Graphs
Zig-zag number
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The notion of zig-zag number was introduced as an attempt to provide a unified algorithmic framework for directed graphs. Nevertheless, little was known about the complexity of computing this directed graph invariant. We prove that deciding whether a directed graph has zig-zag number at most k is in NP for each fixed k≥0. Although for most of the natural decision problems this is an almost trivial result, settling k-zig-zag number in NP is surprisingly difficult. In addition, we prove that 2-zig-zag number is already an NP-hard problem.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2021.09.013