Source author record

Michal Pilipczuk

Michal Pilipczuk appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics Logic in Computer Science math.CO math.LO

Catalog footprint

What is connected

8works

6topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2021arXiv

Finding large induced sparse subgraphs in $C_{>t}$-free graphs in quasipolynomial time

For an integer $t$, a graph $G$ is called {\em{$C_{>t}$-free}} if $G$ does not contain any induced cycle on more than~$t$ vertices. We prove the following statement: for every pair of integers $d$ and $t$ and a CMSO$_2$ statement~$ϕ$, there exists an algorithm that, given an $n$-vertex $C_{>t}$-free graph $G$ with weights on vertices, finds in time $n^{O(\log^4 n)}$ a maximum-weight vertex subset $S$ such that $G[S]$ has degeneracy at most $d$ and satisfies $ϕ$. The running time can be improved to $n^{O(\log^2 n)}$ assuming $G$ is $P_t$-free, that is, $G$ does not contain an induced path on $t$ vertices. This expands the recent results of the authors [to appear at FOCS 2020 and SOSA 2021] on the {\sc{Maximum Weight Independent Set}} problem on $P_t$-free graphs in two directions: by encompassing the more general setting of $C_{>t}$-free graphs, and by being applicable to a much wider variety of problems, such as {\sc{Maximum Weight Induced Forest}} or {\sc{Maximum Weight Induced Planar Graph}}.

preprint2020arXiv

Rankwidth meets stability

We study two notions of being well-structured for classes of graphs that are inspired by classic model theory. A class of graphs $C$ is monadically stable if it is impossible to define arbitrarily long linear orders in vertex-colored graphs from $C$ using a fixed first-order formula. Similarly, monadic dependence corresponds to the impossibility of defining all graphs in this way. Examples of monadically stable graph classes are nowhere dense classes, which provide a robust theory of sparsity. Examples of monadically dependent classes are classes of bounded rankwidth (or equivalently, bounded cliquewidth), which can be seen as a dense analog of classes of bounded treewidth. Thus, monadic stability and monadic dependence extend classical structural notions for graphs by viewing them in a wider, model-theoretical context. We explore this emerging theory by proving the following: - A class of graphs $C$ is a first-order transduction of a class with bounded treewidth if and only if $C$ has bounded rankwidth and a stable edge relation (i.e. graphs from $C$ exclude some half-graph as a semi-induced subgraph). - If a class of graphs $C$ is monadically dependent and not monadically stable, then $C$ has in fact an unstable edge relation. As a consequence, we show that classes with bounded rankwidth excluding some half-graph as a semi-induced subgraph are linearly $χ$-bounded. Our proofs are effective and lead to polynomial time algorithms.

preprint2020arXiv

Shorter Labeling Schemes for Planar Graphs

An \emph{adjacency labeling scheme} for a given class of graphs is an algorithm that for every graph $G$ from the class, assigns bit strings (labels) to vertices of $G$ so that for any two vertices $u,v$, whether $u$ and $v$ are adjacent can be determined by a fixed procedure that examines only their labels. It is known that planar graphs with $n$ vertices admit a labeling scheme with labels of bit length $(2+o(1))\log{n}$. In this work we improve this bound by designing a labeling scheme with labels of bit length $(\frac{4}{3}+o(1))\log{n}$. In graph-theoretical terms, this implies an explicit construction of a graph on $n^{4/3+o(1)}$ vertices that contains all planar graphs on $n$ vertices as induced subgraphs, improving the previous best upper bound of $n^{2+o(1)}$. Our scheme generalizes to graphs of bounded Euler genus with the same label length up to a second-order term. All the labels of the input graph can be computed in polynomial time, while adjacency can be decided from the labels in constant time.

preprint2015arXiv

Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints

In parameterized complexity, it is a natural idea to consider different generalizations of classic problems. Usually, such generalization are obtained by introducing a "relaxation" variable, where the original problem corresponds to setting this variable to a constant value. For instance, the problem of packing sets of size at most $p$ into a given universe generalizes the Maximum Matching problem, which is recovered by taking $p=2$. Most often, the complexity of the problem increases with the relaxation variable, but very recently Abasi et al. have given a surprising example of a problem --- $r$-Simple $k$-Path --- that can be solved by a randomized algorithm with running time $O^*(2^{O(k \frac{\log r}{r})})$. That is, the complexity of the problem decreases with $r$. In this paper we pursue further the direction sketched by Abasi et al. Our main contribution is a derandomization tool that provides a deterministic counterpart of the main technical result of Abasi et al.: the $O^*(2^{O(k \frac{\log r}{r})})$ algorithm for $(r,k)$-Monomial Detection, which is the problem of finding a monomial of total degree $k$ and individual degrees at most $r$ in a polynomial given as an arithmetic circuit. Our technique works for a large class of circuits, and in particular it can be used to derandomize the result of Abasi et al. for $r$-Simple $k$-Path. On our way to this result we introduce the notion of representative sets for multisets, which may be of independent interest. Finally, we give two more examples of problems that were already studied in the literature, where the same relaxation phenomenon happens. The first one is a natural relaxation of the Set Packing problem, where we allow the packed sets to overlap at each element at most $r$ times. The second one is Degree Bounded Spanning Tree, where we seek for a spanning tree of the graph with a small maximum degree.

preprint2015arXiv

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.

preprint2013arXiv

Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?

We prove a number of results around kernelization of problems parameterized by the size of a given vertex cover of the input graph. We provide three sets of simple general conditions characterizing problems admitting kernels of polynomial size. Our characterizations not only give generic explanations for the existence of many known polynomial kernels for problems like q-Coloring, Odd Cycle Transversal, Chordal Deletion, Eta Transversal, or Long Path, parameterized by the size of a vertex cover, but also imply new polynomial kernels for problems like F-Minor-Free Deletion, which is to delete at most k vertices to obtain a graph with no minor from a fixed finite set F. While our characterization captures many interesting problems, the kernelization complexity landscape of parameterizations by vertex cover is much more involved. We demonstrate this by several results about induced subgraph and minor containment testing, which we find surprising. While it was known that testing for an induced complete subgraph has no polynomial kernel unless NP is in coNP/poly, we show that the problem of testing if a graph contains a complete graph on t vertices as a minor admits a polynomial kernel. On the other hand, it was known that testing for a path on t vertices as a minor admits a polynomial kernel, but we show that testing for containment of an induced path on t vertices is unlikely to admit a polynomial kernel.

preprint2011arXiv

Subset feedback vertex set is fixed parameter tractable

The classical Feedback Vertex Set problem asks, for a given undirected graph G and an integer k, to find a set of at most k vertices that hits all the cycles in the graph G. Feedback Vertex Set has attracted a large amount of research in the parameterized setting, and subsequent kernelization and fixed-parameter algorithms have been a rich source of ideas in the field. In this paper we consider a more general and difficult version of the problem, named Subset Feedback Vertex Set (SUBSET-FVS in short) where an instance comes additionally with a set S ? V of vertices, and we ask for a set of at most k vertices that hits all simple cycles passing through S. Because of its applications in circuit testing and genetic linkage analysis SUBSET-FVS was studied from the approximation algorithms perspective by Even et al. [SICOMP'00, SIDMA'00]. The question whether the SUBSET-FVS problem is fixed-parameter tractable was posed independently by Kawarabayashi and Saurabh in 2009. We answer this question affirmatively. We begin by showing that this problem is fixed-parameter tractable when parametrized by |S|. Next we present an algorithm which reduces the given instance to 2^k n^O(1) instances with the size of S bounded by O(k^3), using kernelization techniques such as the 2-Expansion Lemma, Menger's theorem and Gallai's theorem. These two facts allow us to give a 2^O(k log k) n^O(1) time algorithm solving the Subset Feedback Vertex Set problem, proving that it is indeed fixed-parameter tractable.

preprint2010arXiv

The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem)

One of the driving problems in the CSP area is the Dichotomy Conjecture, formulated in 1993 by Feder and Vardi [STOC'93], stating that for any fixed relational structure G the Constraint Satisfaction Problem CSP(G) is either NP--complete or polynomial time solvable. A large amount of research has gone into checking various specific cases of this conjecture. One such variant which attracted a lot of attention in the recent years is the LIST MATRIX PARTITION problem. In 2004 Cameron et al. [SODA'04] classified almost all LIST MATRIX PARTITION variants for matrices of size at most four. The only case which resisted the classification became known as the STUBBORN PROBLEM. In this paper we show a result which enables us to finish the classification - thus solving a problem which resisted attacks for the last six years. Our approach is based on a combinatorial problem known to be at least as hard as the STUBBORN PROBLEM - the 3-COMPATIBLE COLOURING problem. In this problem we are given a complete graph with each edge assigned one of 3 possible colours and we want to assign one of those 3 colours to each vertex in such a way that no edge has the same colour as both of its endpoints. The tractability of the 3-COMPATIBLE COLOURING problem has been open for several years and the best known algorithm prior to this paper is due to Feder et al. [SODA'05] - a quasipolynomial algorithm with a n^O(log n / log log n) time complexity. In this paper we present a polynomial-time algorithm for the 3-COMPATIBLE COLOURING problem and consequently we prove a dichotomy for the k-COMPATIBLE COLOURING problem.