Steiner connectivity problems in hypergraphs

DOI10.1016/J.IPL.2023.106428MaRDI QIDQ6072212zbMATH OpenOpenAlexFDO

Authors Florian Hoersch, Zoltán Szigeti

Publication date 12 October 2023

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityconnectivityhypergraphsorientationSteiner trees

Mathematics Subject Classification ID

Connectivity (05C40) Hypergraphs (05C65)

Abstract: We say that a tree $T$ is an $S$-Steiner tree if $SsubseteqV(T)$ and a hypergraph is an $S$-Steiner hypertree if it can be trimmed to an $S$-Steiner tree. We prove that it is NP-complete to decide, given a hypergraph $mathcalH$ and some $SsubseteqV(mathcalH)$, whether there is a subhypergraph of $mathcalH$ which is an $S$-Steiner hypertree. As corollaries, we give two negative results for two Steiner orientation problems in hypergraphs. Firstly, we show that it is NP-complete to decide, given a hypergraph $mathcalH$, some $rinV(mathcalH)$ and some $SsubseteqV(mathcalH)$, whether this hypergraph has an orientation in which every vertex of $S$ is reachable from $r$. Secondly, we show that it is NP-complete to decide, given a hypergraph $mathcalH$ and some $SsubseteqV(mathcalH)$, whether this hypergraph has an orientation in which any two vertices in $S$ are mutually reachable from each other. This answers a longstanding open question of the Egerv'ary Research group. We further show that it is NP-complete to decide if a given hypergraph has a well-balanced orientation. On the positive side, we show that the problem of finding a Steiner hypertree and the first orientation problem can be solved in polynomial time if the number of terminals $|S|$ is fixed.

Recommendations

• Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs
• Minimum spanning hypertrees
• The steiner problem in the hypercube

Cites work

• scientific article; zbMATH DE number 3512137 (Why is no real title available?)
• A fast algorithm for Steiner trees
• An improved LP-based approximation for Steiner tree
• Edge-disjoint trees containing some given vertices in a graph
• Graph minors. XIII: The disjoint paths problem
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• On decomposing a hypergraph into \(k\) connected sub-hypergraphs
• On the orientation of graphs and hypergraphs
• Packing Steiner trees with identical terminal sets
• Packing of Steiner trees and \(S\)-connectors in graphs
• Reducibility among combinatorial problems
• The disjoint paths problem in quadratic time
• The steiner problem in graphs

This page was built for publication: Steiner connectivity problems in hypergraphs

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