16 citations · 188 across the 122 of their papers we have counts for
14 papers · 1 filter
A Note on the Parameterised Complexity of Coverability in Vector Addition Systems
Michał Pilipczuk, Sylvain Schmitz, Henry Sinclair-Banks
We investigate the parameterised complexity of the classic coverability problem for vector addition systems (VAS): given a finite set of vectors , an initi…
On Integer Programs That Look Like Paths
Marcin Briański, Alexandra Lassota, Kristýna Pekárková +2
Solving integer programs of the form is, in general, $…
Box-Reachability in Vector Addition Systems
Shaull Almagor, Itay Hasson, Michał Pilipczuk +1
We consider a variant of reachability in Vector Addition Systems (VAS) dubbed \emph{box reachability}, whereby a vector is box-reachable from in a VAS i…
First-order transducibility among classes of sparse graphs
Jakub Gajarský, Jeremi Gładkowski, Jan Jedelský +2
We prove several negative results about first-order transducibility for classes of sparse graphs: - for every , the class of graphs of treewidth at most is…
Strong odd colorings in graph classes of bounded expansion
Michał Pilipczuk
We prove that for every and a graph class of bounded expansion , there exists some so that every graph from admits a…
Separability Properties of Monadically Dependent Graph Classes
Édouard Bonnet, Samuel Braunfeld, Ioannis Eleftheriadis +5
A graph class is monadically dependent if one cannot interpret all graphs in colored graphs from using a fixed first-order interpretation. We prove that m…
Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
Michał Pilipczuk, Giannos Stamoulis, Michał Włodarczyk
In the Disjoint Shortest Paths problem one is given a graph and a set of vertex pairs. The question is whether there exist verte…
On graphs coverable by chubby shortest paths
Meike Hatzel, Michał Pilipczuk
Dumas, Foucaud, Perez, and Todinca [SIAM J. Disc. Math., 2024] proved that if the vertex set of a graph can be covered by shortest paths, then the pathwidth of is bound…
Low rank MSO
Mikołaj Bojańczyk, Michał Pilipczuk, Wojciech Przybyszewski +2
We introduce a new logic for describing properties of graphs, which we call low rank MSO. This is the fragment of monadic second-order logic in which set quantification is restrict…
Faster diameter computation in graphs of bounded Euler genus
Kacper Kluk, Marcin Pilipczuk, Michał Pilipczuk +1
We show that for any fixed integer , there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected -vert…
On coarse tree decompositions and coarse balanced separators
Tara Abrishami, Jadwiga Czyżewska, Kacper Kluk +3
It is known that there is a linear dependence between the treewidth of a graph and its balanced separator number: the smallest integer such that for every weighing of the verti…
Obstructions and dualities for matroid depth parameters
Jakub Gajarský, Kristýna Pekárková, Michał Pilipczuk
Contraction-depth is considered to be one of the analogues of graph tree-depth in the matroid setting. In this paper, we investigate structural properties of contraction-de…
3D-grids are not transducible from planar graphs
Jakub Gajarský, Michał Pilipczuk, Filip Pokrývka
We prove that the class of 3D-grids is cannot be transduced from planar graphs, and more generally, from any class of graphs of bounded Euler genus. To prove our result, we introdu…
Graph classes through the lens of logic
Michał Pilipczuk
Graph transformations definable in logic can be described using the notion of transductions. By understanding transductions as a basic embedding mechanism, which captures the possi…