Problems on Group-labeled Matroid Bases
<|reference_start|>Problems on Group-labeled Matroid Bases: 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|\le 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.<|reference_end|>
@article{hörsch2024problems,
    title={Problems on Group-labeled Matroid Bases},
    author={Florian H"orsch, Andr'as Imolay, Ryuhei Mizutani, Taihei Oki,
  Tam'as Schwarcz},
    journal={arXiv preprint arXiv:2402.16259},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.16259},
    primaryClass={cs.DM cs.DS math.CO}
}