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

DOI10.1016/J.DISC.2024.113895MaRDI QIDQ6204322zbMATH OpenOpenAlexWikidataFDO

Authors Emeric Gioan, Michel Las Vergnas

Publication date 27 March 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

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)

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.

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

Cites work

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

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)