CISPA
Browse

Problems on Group-Labeled Matroid Bases

Download (855.99 kB)
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 Schwarcz
Consider 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

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC