Recognising graphic and matroidal connectivity functions

DOI10.1016/J.DISC.2020.112093zbMATH Open1448.05029arXiv2007.04469OpenAlexW3080288465MaRDI QIDQ2005684FDOQ2005684

Authors: Nathan Bowler, Susan Jowett 

Publication date: 8 October 2020

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

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.

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

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

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)

Cites Work

• Decomposition of regular matroids
• Title not available (Why is that?)
• Lectures on matroids
• Recognizing graphic matroids
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• On the efficiency of representability tests for matroids
• Title not available (Why is that?)

Cited In (3)

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

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)