Lukas Mach
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Lukas Mach has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Ivan Bliznets
University of Groningen
2 shared publications Pawel Komosa
Institute of Informatics University of Warsaw Poland
2 shared publications- Anita Liebenau
School of Mathematics and Statistics UNSW Sydney 2052 NSW Australia
1 shared publication - Daniel Kral
Masaryk University
1 shared publication - Frantisek Kardos
LABRI University of Bordeaux France
1 shared publication - Marek Cygan
University of Warsaw
1 shared publication
Latest Publications
- Open Access
First order convergence of matroids
The model theory based notion of the first order convergence unifies the notions of the left-convergence for dense structures and the Benjamini-Schramm convergence for sparse structures. It is known that every first order convergent sequence of graphs with bounded tree-depth can be represented by an analytic limit object called a limit modeling. We establish the matroid counterpart of this result: every first order convergent sequence of matroids with bounded branch-depth representable over a fixed finite field has a limit modeling, i.e., there exists an infinite matroid with the elements forming a probability space that has asymptotically the same first order properties. We show that neither of the bounded branch-depth assumption nor the representability assumption can be removed.
Open AccessFirst order convergence of matroids
The model theory based notion of the first order convergence unifies the notions of the left-convergence for dense structures and the Benjamini-Schramm convergence for sparse structures. It is known that every first order convergent sequence of graphs with bounded tree-depth can be represented by an analytic limit object called a limit modeling. We establish the matroid counterpart of this result: every first order convergent sequence of matroids with bounded branch-depth representable over a fixed finite field has a limit modeling, i.e., there exists an infinite matroid with the elements forming a probability space that has asymptotically the same first order properties. We show that neither of the bounded branch-depth assumption nor the representability assumption can be removed.
- Open Access
Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
In this work, we focus on several completion problems for subclasses of chordal graphs: Minimum Fill-In, Interval Completion, Proper Interval Completion, Threshold Completion, and Trivially Perfect Completion. In these problems, the task is to add at most k edges to a given graph in order to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds for all these problems, as well as for the related Chain Completion problem: Assuming the Exponential Time Hypothesis, none of these problems can be solved in time 2^O(n^(1/2) / log^c n) or 2^O(k^(1/4) / log^c k) n^O(1), for some integer c. Assuming the non-existence of a subexponential-time approximation scheme for Min Bisection on d-regular graphs, for some constant d, none of these problems can be solved in time 2^o(n) or 2^o(sqrt(k)) n^O(1). For all the aforementioned completion problems, apart from Proper Interval Completion, FPT algorithms with running time of the form 2^O(sqrt(k) log k) n^O(1) are known. Thus, the second result proves that a significant improvement of any of these algorithms would lead to a surprising breakthrough in the design of approximation algorithms for Min Bisection. To prove our results, we use a reduction methodology based on combining the classic approach of starting with a sparse instance of 3-Sat, prepared using the Sparsification Lemma, with the existence of almost linear-size Probabilistically Checkable Proofs (PCPs). Apart from our main results, we also obtain lower bounds excluding the existence of subexponential algorithms for the Optimum Linear Arrangement problem, as well as improved, yet still not tight, lower bounds for Feedback Arc Set in Tournaments.
Open AccessLower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
In this work, we focus on several completion problems for subclasses of chordal graphs: Minimum Fill-In, Interval Completion, Proper Interval Completion, Threshold Completion, and Trivially Perfect Completion. In these problems, the task is to add at most k edges to a given graph in order to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds for all these problems, as well as for the related Chain Completion problem: Assuming the Exponential Time Hypothesis, none of these problems can be solved in time 2^O(n^(1/2) / log^c n) or 2^O(k^(1/4) / log^c k) n^O(1), for some integer c. Assuming the non-existence of a subexponential-time approximation scheme for Min Bisection on d-regular graphs, for some constant d, none of these problems can be solved in time 2^o(n) or 2^o(sqrt(k)) n^O(1). For all the aforementioned completion problems, apart from Proper Interval Completion, FPT algorithms with running time of the form 2^O(sqrt(k) log k) n^O(1) are known. Thus, the second result proves that a significant improvement of any of these algorithms would lead to a surprising breakthrough in the design of approximation algorithms for Min Bisection. To prove our results, we use a reduction methodology based on combining the classic approach of starting with a sparse instance of 3-Sat, prepared using the Sparsification Lemma, with the existence of almost linear-size Probabilistically Checkable Proofs (PCPs). Apart from our main results, we also obtain lower bounds excluding the existence of subexponential algorithms for the Optimum Linear Arrangement problem, as well as improved, yet still not tight, lower bounds for Feedback Arc Set in Tournaments.
- Open Access
Kernelization lower bound for Permutation Pattern Matching
A permutation $\pi$ contains a permutation $\sigma$ as a pattern if it contains a subsequence of length $|\sigma|$ whose elements are in the same relative order as in the permutation $\sigma$. This notion plays a major role in enumerative combinatorics. We prove that the problem does not have a polynomial kernel (under the widely believed complexity assumption $\mbox{NP} \not\subseteq \mbox{co-NP}/\mbox{poly}$) by introducing a new polynomial reduction from the clique problem to permutation pattern matching.Open AccessKernelization lower bound for Permutation Pattern Matching
A permutation $\pi$ contains a permutation $\sigma$ as a pattern if it contains a subsequence of length $|\sigma|$ whose elements are in the same relative order as in the permutation $\sigma$. This notion plays a major role in enumerative combinatorics. We prove that the problem does not have a polynomial kernel (under the widely believed complexity assumption $\mbox{NP} \not\subseteq \mbox{co-NP}/\mbox{poly}$) by introducing a new polynomial reduction from the clique problem to permutation pattern matching. - Open Access
Amalgam width of matroids
We introduce a new matroid width parameter based on the operation of matroid amalgamation, which we call amalgam-width. The parameter is linearly related to branch-width on finitely representable matroids (which is not possible for branch-width). In particular, any property expressible in the monadic second order logic can be decided in linear time for matroids with bounded amalgam-width. We also prove that the Tutte polynomial can be computed in polynomial time for matroids with bounded amalgam width.
Open AccessAmalgam width of matroids
We introduce a new matroid width parameter based on the operation of matroid amalgamation, which we call amalgam-width. The parameter is linearly related to branch-width on finitely representable matroids (which is not possible for branch-width). In particular, any property expressible in the monadic second order logic can be decided in linear time for matroids with bounded amalgam-width. We also prove that the Tutte polynomial can be computed in polynomial time for matroids with bounded amalgam width.