Recognising graphic and matroidal connectivity functions

DOI10.1016/J.DISC.2020.112093MaRDI QIDQ2005684zbMATHOpenAlexFDO

Authors Nathan Bowler, Susan Jowett

Publication date 8 October 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

matroidsrecognition problemsconnectivity functions

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Graph theory (05C99)

Abstract: A {em connectivity function} on a set $E$ is a function $lambda:2^{E}ightarrowmathbbR$ such that $lambda(emptyset)=0$, that $lambda(X)=lambda(E-X)$ for all $XsubseteqE$, and that $lambda(XcapY)+lambda(XcupY)leqlambda(X)+lambda(Y)$ for all $X,YsubseteqE$. Graphs, matroids and, more generally, polymatroids have associated connectivity functions. In this paper we give a method for identifying when a connectivity function comes from a graph. This method uses no more than a polynomial number of evaluations of the connectivity function. In contrast, we show that the problem of identifying when a connectivity function comes from a matroid cannot be solved in polynomial time. We also show that the problem of identifying when a connectivity function is not that of a matroid cannot be solved in polynomial time.

Recommendations

• Connectivity functions and polymatroids
• On the connectivity function of a matroid
• The reconstruction of a matroid from its connectivity function
• On the connectivity function of a binary matroid
• Connectivity of submodular functions

Cites work

• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 3378962 (Why is no real title available?)
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Decomposition of regular matroids
• Lectures on matroids
• On the efficiency of representability tests for matroids
• Recognizing graphic matroids

Cited in

(3)

• Connectivity of submodular functions
• Connectivity functions and polymatroids
• Bounding branch-width

This page was built for publication: Recognising graphic and matroidal connectivity functions

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