# Problems on Group-Labeled Matroid Bases

conference contribution

posted on 2024-07-25, 12:38 authored by Florian HörschFlorian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, Tamás SchwarczConsider a matroid equipped with a labeling of its ground set to an abelian group. We define the label of a subset of the ground set as the sum of the labels of its elements. We study a collection of problems on finding bases and common bases of matroids with restrictions on their labels. For zero bases and zero common bases, the results are mostly negative. While finding a non-zero basis of a matroid is not difficult, it turns out that the complexity of finding a non-zero common basis depends on the group. Namely, we show that the problem is hard for a fixed group if it contains an element of order two, otherwise it is polynomially solvable. As a generalization of both zero and non-zero constraints, we further study F-avoiding constraints where we seek a basis or common basis whose label is not in a given set F of forbidden labels. Using algebraic techniques, we give a randomized algorithm for finding an F-avoiding common basis of two matroids represented over the same field for finite groups given as operation tables. The study of F-avoiding bases with groups given as oracles leads to a conjecture stating that whenever an F-avoiding basis exists, an F-avoiding basis can be obtained from an arbitrary basis by exchanging at most |F| elements. We prove the conjecture for the special cases when |F| ≤ 2 or the group is ordered. By relying on structural observations on matroids representable over fixed, finite fields, we verify a relaxed version of the conjecture for these matroids. As a consequence, we obtain a polynomial-time algorithm in these special cases for finding an F-avoiding basis when |F| is fixed.

## History

## Editor

Bringmann K ; Grohe M ; Puppis G ; Svensson O## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

International Colloquium on Automata Languages and Programming (ICALP)## Journal

51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)## Volume

297## Page Range

86:1-86:20## Publisher

Schloss Dagstuhl – Leibniz-Zentrum für Informatik## BibTeX

@inproceedings{Hörsch:Imolay:Mizutani:Oki:Schwarcz:2024, title = "Problems on Group-Labeled Matroid Bases", author = "Hörsch, Florian" AND "Imolay, András" AND "Mizutani, Ryuhei" AND "Oki, Taihei" AND "Schwarcz, Tamás", editor = "Bringmann, Karl" AND "Grohe, Martin" AND "Puppis, Gabriele" AND "Svensson, Ola", year = 2024, month = 7, journal = "51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)", pages = "86:1--86:20", publisher = "Schloss Dagstuhl – Leibniz-Zentrum für Informatik", issn = "1868-8969", doi = "10.4230/LIPIcs.ICALP.2024.86" }## Usage metrics

## Categories

No categories selected## Keywords

## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC