Make a graph singly connected by edge orientations

DOI10.1007/978-3-031-34347-6_19arXiv2306.02065OpenAlexW4379134874MaRDI QIDQ6182906FDOQ6182906

Authors: Tim A. Hartmann, Komal Muluk 

Publication date: 22 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: A directed graph $D$ is singly connected if for every ordered pair of vertices $(s,t)$, there is at most one path from $s$ to $t$ in $D$. Graph orientation problems ask, given an undirected graph $G$, to find an orientation of the edges such that the resultant directed graph $D$ has a certain property. In this work, we study the graph orientation problem where the desired property is that $D$ is singly connected. Our main result concerns graphs of a fixed girth $g$ and coloring number $c$. For every $g,cgeq3$, the problem restricted to instances of girth $g$ and coloring number $c$, is either NP-complete or in P. As further algorithmic results, we show that the problem is NP-hard on planar graphs and polynomial time solvable distance-hereditary graphs.

Full work available at URL: https://arxiv.org/abs/2306.02065

zbMATH Keywords

chromatic numberdirected graphsgirth

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Introduction to algorithms
• Graph Theory and Probability
• Distance-hereditary graphs
• Determining uni-connectivity in directed graphs
• An \(O(|V|^2)\) algorithm for single connectedness
• On the complexity of singly connected vertex deletion
• On testing single connectedness in directed graphs and some related problems
• Graph theory
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• Completely separable graphs
• Title not available (Why is that?)
• Noncrossing Subgraphs in Topological Layouts

This page was built for publication: Make a graph singly connected by edge orientations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6182906)