Computing the fully optimal spanning tree of an ordered bipolar directed graph

DOI10.1016/J.DISC.2024.113895arXiv1807.06552OpenAlexW2883292267WikidataQ128542127 ScholiaQ128542127MaRDI QIDQ6204322FDOQ6204322

Authors: Emeric Gioan, Michel Las Vergnas 

Publication date: 27 March 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: It has been previously shown by the authors that a directed graph on a linearly ordered set of edges (ordered graph) with adjacent unique source and sink (bipolar digraph) has a unique fully optimal spanning tree, that satisfies a simple criterion on fundamental cycle/cocycle directions. This result yields, for any ordered graph, a canonical bijection between bipolar orientations and spanning trees with internal activity 1 and external activity 0 in the sense of the Tutte polynomial. This bijection can be extended to all orientations and all spanning trees, yielding the active bijection, presented for graphs in a companion paper. In this paper, we specifically address the problem of the computation of the fully optimal spanning tree of an ordered bipolar digraph. In contrast with the inverse mapping, built by a straightforward single pass over the edge set, the direct computation is not easy and had previously been left aside. We give two independent constructions. The first one is a deletion/contraction recursion, involving an exponential number of minors. It is structurally significant but it is efficient only for building the whole bijection (i.e. all images) at once. The second one is more complicated and is the main contribution of the paper. It involves just one minor for each edge of the resulting spanning tree, and it is a translation and an adaptation in the case of graphs, in terms of weighted cocycles, of a general geometrical linear programming type algorithm, which allows for a polynomial time complexity.

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

Recommendations

• The active bijection for graphs
• A linear programming construction of fully optimal bases in graphs and hyperplane arrangements
• Activity preserving bijections between spanning trees and orientations in graphs
• The active bijection in graphs, hyperplane arrangements, and oriented matroids, 1: the fully optimal basis of a bounded region
• scientific article; zbMATH DE number 177570

zbMATH Keywords

computational complexitylinear programmingTutte polynomialspanning treeactive bijectionbipolar directed graph

Mathematics Subject Classification ID

Linear programming (90C05) Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• A Contribution to the Theory of Chromatic Polynomials
• Oriented Matroids
• Geometric algorithms and combinatorial optimization
• Digraphs
• A higher invariant for matroids
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• The active bijection between regions and simplices in supersolvable arrangements of hyperplanes
• Title not available (Why is that?)
• Activity preserving bijections between spanning trees and orientations in graphs
• The active bijection in graphs, hyperplane arrangements, and oriented matroids, 1: the fully optimal basis of a bounded region
• Bases, reorientations, and linear programming, in uniform and rank-3 oriented matroids
• A linear programming construction of fully optimal bases in graphs and hyperplane arrangements
• Fully Optimal Bases and the Active Bijection in Graphs, Hyperplane Arrangements, and Oriented Matroids
• The active bijection for graphs
• The Tutte polynomial of oriented matroids

This page was built for publication: Computing the fully optimal spanning tree of an ordered bipolar directed graph

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