thesis_access.pdf (661.5 kB)

Matroids, Complexity and Computation

thesis
posted on 2021-11-13, 12:56 authored by Snook, Michael

The node deletion problem on graphs is: given a graph and integer k, can we delete no more than k vertices to obtain a graph that satisfies some property π. Yannakakis showed that this problem is NP-complete for an infinite family of well- defined properties. The edge deletion problem and matroid deletion problem are similar problems where given a graph or matroid respectively, we are asked if we can delete no more than k edges/elements to obtain a graph/matroid that satisfies a property π. We show that these problems are NP-hard for similar well-defined infinite families of properties.  In 1991 Vertigan showed that it is #P-complete to count the number of bases of a representable matroid over any fixed field. However no publication has been produced. We consider this problem and show that it is #P-complete to count the number of bases of matroids representable over any infinite fixed field or finite fields of a fixed characteristic.  There are many different ways of describing a matroid. Not all of these are polynomially equivalent. That is, given one description of a matroid, we cannot create another description for the same matroid in time polynomial in the size of the first description. Due to this, the complexity of matroid problems can vary greatly depending on the method of description used. Given one description a problem might be in P while another description gives an NP-complete problem. Based on these interactions between descriptions, we create and study the hierarchy of all matroid descriptions and generalize this to all descriptions of countable objects.

2013-01-01

2013-01-01

Publisher

Te Herenga Waka—Victoria University of Wellington

Mathematics

Degree Grantor

Te Herenga Waka—Victoria University of Wellington

Doctoral

Degree Name

Doctor of Philosophy

ANZSRC Type Of Activity code

970101 Expanding Knowledge in the Mathematical Sciences

Victoria University of Wellington Item Type

Awarded Doctoral Thesis

en_NZ

Victoria University of Wellington School

School of Mathematics, Statistics and Operations Research