Make a graph singly connected by edge orientations

DOI10.1007/978-3-031-34347-6_19MaRDI QIDQ6182906zbMATH OpenOpenAlexFDO

Authors Tim A. Hartmann, Komal Muluk

Publication date 22 December 2023

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

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)

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.

Cites work

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

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)