Algorithmic aspects of matroid minors
Abstract
The proposed work is aimed solving a variety of computational problems for matrices defined over finite fields. These problems have applications in optimization and coding theory. The research will be based on the deep structure theory developed by the PI for matroids representable over finite fields. Objective Matroid theory provides a unifying framework for problems involving graphs and matrices, and has applications in diverse areas such as combinatorial optimization, coding theory, information theory, electrical engineering, and computational biology. In recent years, there have been very exciting advances in the area of matroid representation theory, more specifically for matroids representable over finite fields. In particular, the PI, under previous ONR funding, solved an outstanding open problem for matroids representable over finite fields by show that for any infinite set of such matroids, there exists one that is isomorphic to a minor of another. This was proved by developing a structure theory for matroid representable over finite fields. The objective of this research is to investigate algorithmic implications of this structure theory. That is, can the theory be used to develop efficient algorithms for a variety of matrix problems? Approach The proposed research will focus on the following algorithmic problems: 1) Characterize the tuples (M; a; b; c) where M is a representable matroid and a, b, and c are distinct elements of M such that no circuit of M contains all three. The solution of this problem would lead to a nice constructive version of the matroid structure theory developed under the previous ONR grant. 2) Find an efficient algorithm for recognizing frame matroids. Frame matroids are those matroids that are representable by a matrix having at most two nonzero. Such matrices arise in a number of interesting optimization problems. 3) Show that girth can be computed efficiently in any minor-closed class of binary matroids. The girth of a binary matroid is closely related to computing the Hamming distance of a binary code. Thus, the solution of this problem would have an impact on coding theory. Overall Merits and ONR Mission Relevance Networks, whether physical or virtual, are of fundamental relevance to the Navy s mission. Matroids are one of the the mathematical structures that underlie networks, and an improved mathematical understanding of matroids can lead to enhanced network capabilities for the Navy.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2016
- Source ID
- N000141512079
Entities
People
- James Geelen
Organizations
- Office of Naval Research
- United States Navy
- University of Waterloo