Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-26T00:46:01.386Z Has data issue: false hasContentIssue false
  • English
  • Français

Recognizing Polymatroids Associated with Hypergraphs

Published online by Cambridge University Press:  12 September 2008

Dirk Vertigan  and
Geoff Whittle
Dirk Vertigan
Affiliation:
Mathematical Institute, Oxford University, England
Geoff Whittle
Affiliation:
Department of Mathematics, University of Tasmania, Hobart, Tasmania 7001, Australia
Get access Rights & Permissions [Opens in a new window]

Abstract

Two natural classes of polymatroids can be associated with hypergraphs: the so-called Boolean and hypergraphic polymatroids. Boolean polymatroids carry virtually all the structure of hypergraphs; hypergraphic polymatroids generalize graphic matroids. This paper considers algorithmic problems associated with recognizing members of these classes. Let k be a fixed positive integer and assume that the k-polymatroid ρ is presented via a rank oracle. We present an algorithm that determines in polynomial time whether ρ is Boolean, and if it is, finds the hypergraph. We also give an algorithm that decides in polynomial time whether ρ is the hypergraphic polymatroid associated with a given hypergraph. Other structure-theoretic results are also given.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 2 , Issue 4 , December 1993 , pp. 519 - 530
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Downey, R. and Fellows, M. (1992) Fixed Parameter Intractability. Proceedings: Structure in Complexity, Seventh Annual Conference, IEEE 36–50.Google Scholar
[2]Helgason, T. (1974) Aspects of the theory of hypermatroids. In: Berge, C. and Ray-Chaudhuri, D. K. (eds.) Hypergraph Seminar. Lecture Notes in Math. 411, Springer-Verlag 191–214.Google Scholar
[3]Ingleton, A. W. (1977) Transversal matroids and related structures. In: Aigner, M. (ed.) Higher Combinatorics, D. Riedel, Dordrecht.Google Scholar
[4]Lovász, L. and Plummer, M. D. (1986) Matching Theory. Ann. Discrete Math. 29, North-Holland, Amsterdam.Google Scholar
[5]Robinson, G. C. and Welsh, D. J. A. (1980) The computational complexity of matroid properties. Math. Proc. Camb. Phil. Soc. 87 29–45.CrossRefGoogle Scholar
[6]Seymour, P. D. (1981) Recognizing graphic matroids. Combinatorica 1 75–78.CrossRefGoogle Scholar
[7]Tutte, W. T. (1960) An algorithm for determining whether a given binary matroid is graphic. Proc. Amer. Math. Soc. 11 905–917.Google Scholar
[8]Tutte, W. T. (1984) Graph Theory. Encyclopedia of Mathematics and its Applications 21, Addison-Wesley.Google Scholar
[9]Whittle, G. (1992) A geometric theory of hypergraph colouring. Aequationes Mathematicae 43 45–58.CrossRefGoogle Scholar
[10]Whitney, H. (1933) 2-isomorphic graphs. Amer. J. Math. 55 73–84.CrossRefGoogle Scholar