×

A parameterized view on matroid optimization problems. (English) Zbl 1180.90275

Summary: Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for designing polynomial-time algorithms. However, several natural matroid problems, such as 3-matroid intersection, are NP-hard. Here we investigate these problems from the parameterized complexity point of view: instead of the trivial \(n^{O(k)}\) time brute force algorithm for finding a \(k\)-element solution, we try to give algorithms with uniformly polynomial (i.e., \(f(k)\cdot n^{O(1)})\) running time. The main result is that if the ground set of a represented linear matroid is partitioned into blocks of size \(\ell \), then we can determine in randomized time \(f(k,\ell )\cdot n^{O(1)}\) whether there is an independent set that is the union of \(k\) blocks. As a consequence, algorithms with similar running time are obtained for other problems such as finding a \(k\)-element set in the intersection of \(\ell \) matroids, or finding \(k\) terminals in a network such that each of them can be connected simultaneously to the source by \(\ell \) disjoint paths.

MSC:

90C27 Combinatorial optimization
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI

References:

[1] Alon, N.; Yuster, R.; Zwick, U., Finding and counting given length cycles, Algorithmica, 17, 3, 209-223 (1997) · Zbl 0865.68093
[2] Downey, R. G.; Fellows, M. R., (Parameterized Complexity. Parameterized Complexity, Monographs in Computer Science (1999), Springer-Verlag: Springer-Verlag New York)
[3] Flum, J.; Grohe, M., Parameterized Complexity Theory (2006), Springer-Verlag: Springer-Verlag Berlin · Zbl 1143.68016
[4] (Graham, R. L.; Grötschel, M.; Lovász, L., Handbook of Combinatorics, Vol. 1, 2 (1995), Elsevier Science B.V.: Elsevier Science B.V. Amsterdam) · Zbl 0833.05001
[5] Lovász, L., Flats in matroids and geometric graphs, (Combinatorial Surveys. Combinatorial Surveys, Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977 (1977), Academic Press: Academic Press London), 45-86 · Zbl 0361.05027
[6] Lovász, L., Matroid matching and some applications, J. Combin. Theory Ser. B, 28, 2, 208-236 (1980) · Zbl 0444.05031
[7] Mac Lane, S.; Birkhoff, G., Algebra (1988), Chelsea Publishing Co.: Chelsea Publishing Co. New York · Zbl 0641.12001
[8] Marx, D., Parameterized coloring problems on chordal graphs, Theoret. Comput. Sci., 351, 3, 407-424 (2006) · Zbl 1087.68072
[9] Monien, B., How to find long paths efficiently, (Analysis and Design of Algorithms for Combinatorial Problems. Analysis and Design of Algorithms for Combinatorial Problems, Udine, 1982. Analysis and Design of Algorithms for Combinatorial Problems. Analysis and Design of Algorithms for Combinatorial Problems, Udine, 1982, North-Holland Math. Stud., vol. 109 (1985), North-Holland: North-Holland Amsterdam), 239-254 · Zbl 0603.68069
[10] Perfect, H., Applications of Menger’s graph theorem, J. Math. Anal. Appl., 22, 96-111 (1968) · Zbl 0157.55301
[11] Plehn, J.; Voigt, B., Finding minimally weighted subgraphs, (Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Berlin, 1990. Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Berlin, 1990, Lecture Notes in Comput. Sci., vol. 484 (1991), Springer: Springer Berlin), 18-29 · Zbl 0768.68170
[12] Recski, A., Matroid theory and its applications in electric network theory and statics, (Algorithms and Combinatorics, vol. 6 (1989), Springer-Verlag: Springer-Verlag Berlin, New York), Akadémiai Kiadó, Budapest · Zbl 0723.05023
[13] Schwartz, J. T., Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach., 27, 4, 701-717 (1980) · Zbl 0452.68050
[14] Shoup, V., Fast construction of irreducible polynomials over finite fields, J. Symbolic Comput., 17, 5, 371-391 (1994) · Zbl 0815.11059
[15] Zippel, R., Probabilistic algorithms for sparse polynomials, (Symbolic and Algebraic Computation. Symbolic and Algebraic Computation, EUROSAM’79, Internat. Sympos., Marseille, 1979. Symbolic and Algebraic Computation. Symbolic and Algebraic Computation, EUROSAM’79, Internat. Sympos., Marseille, 1979, Lecture Notes in Comput. Sci., vol. 72 (1979), Springer: Springer Berlin), 216-226 · Zbl 0418.68040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.