BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Michał Pilipczuk

Michał Pilipczuk contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDiscrete Mathematicsmath.COLogic in Computer ScienceComputational ComplexityFormal Languages and Automata TheoryComputer Science and Game Theorymath.LOComputational Geometry

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
45works
0followers
9topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

45 published item(s)

preprint2023arXiv

Simpler and faster algorithms for detours in planar digraphs

In the directed detour problem one is given a digraph $G$ and a pair of vertices $s$ and~$t$, and the task is to decide whether there is a directed simple path from $s$ to $t$ in $G$ whose length is larger than $\mathsf{dist}_{G}(s,t)$. The more general parameterized variant, directed long detour, asks for a simple $s$-to-$t$ path of length at least $\mathsf{dist}_{G}(s,t)+k$, for a given parameter $k$. Surprisingly, it is still unknown whether directed detour is polynomial-time solvable on general digraphs. However, for planar digraphs, Wu and Wang~[Networks, '15] proposed an $\mathcal{O}(n^3)$-time algorithm for directed detour, while Fomin et al.~[STACS 2022] gave a $2^{\mathcal{O}(k)}\cdot n^{\mathcal{O}(1)}$-time fpt algorithm for directed long detour. The algorithm of Wu and Wang relies on a nontrivial analysis of how short detours may look like in a plane embedding, while the algorithm of Fomin et al.~is based on a reduction to the $§$-disjoint paths problem on planar digraphs. This latter problem is solvable in polynomial time using the algebraic machinery of Schrijver~[SIAM~J.~Comp.,~'94], but the degree of the obtained polynomial factor is huge. In this paper we propose two simple algorithms: we show how to solve, in planar digraphs, directed detour in time $\mathcal{O}(n^2)$ and directed long detour in time $2^{\mathcal{O}(k)}\cdot n^4 \log n$. In both cases, the idea is to reduce to the $2$-disjoint paths problem in a planar digraph, and to observe that the obtained instances of this problem have a certain topological structure that makes them amenable to a direct greedy strategy.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Bounding generalized coloring numbers of planar graphs using coin models

We study Koebe orderings of planar graphs: vertex orderings obtained by modelling the graph as the intersection graph of pairwise internally-disjoint discs in the plane, and ordering the vertices by non-increasing radii of the associated discs. We prove that for every $d\in \mathbb{N}$, any such ordering has $d$-admissibility bounded by $O(d/\ln d)$ and weak $d$-coloring number bounded by $O(d^4 \ln d)$. This in particular shows that the $d$-admissibility of planar graphs is bounded by $O(d/\ln d)$, which asymptotically matches a known lower bound due to Dvořák and Siebertz.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Computing treedepth in polynomial space and linear fpt time

The treedepth of a graph $G$ is the least possible depth of an elimination forest of $G$: a rooted forest on the same vertex set where every pair of vertices adjacent in $G$ is bound by the ancestor/descendant relation. We propose an algorithm that given a graph $G$ and an integer $d$, either finds an elimination forest of $G$ of depth at most $d$ or concludes that no such forest exists; thus the algorithm decides whether the treedepth of $G$ is at most $d$. The running time is $2^{O(d^2)}\cdot n^{O(1)}$ and the space usage is polynomial in $n$. Further, by allowing randomization, the time and space complexities can be improved to $2^{O(d^2)}\cdot n$ and $d^{O(1)}\cdot n$, respectively. This improves upon the algorithm of Reidl et al. [ICALP 2014], which also has time complexity $2^{O(d^2)}\cdot n$, but uses exponential space.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Graphs of bounded twin-width are quasi-polynomially $χ$-bounded

We prove that for every $t\in \mathbb{N}$ there is a constant $γ_t$ such that every graph with twin-width at most $t$ and clique number $ω$ has chromatic number bounded by $2^{γ_t \log^{4t+3} ω}$. In other words, we prove that graph classes of bounded twin-width are quasi-polynomially $χ$-bounded. This provides a significant step towards resolving the question of Bonnet et al. [ICALP 2021] about whether they are polynomially $χ$-bounded.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On objects dual to tree-cut decompositions

Tree-cut width is a graph parameter introduced by Wollan that is an analogue of treewidth for the immersion order on graphs in the following sense: the tree-cut width of a graph is functionally equivalent to the largest size of a wall that can be found in it as an immersion. In this work we propose a variant of the definition of tree-cut width that is functionally equivalent to the original one, but for which we can state and prove a tight duality theorem relating it to naturally defined dual objects: appropriately defined brambles and tangles. Using this result we also propose a game characterization of tree-cut width.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Transducing paths in graph classes with unbounded shrubdepth

Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class $\mathscr{C}$ can be $\mathsf{FO}$-transduced from a class of bounded-height trees (that is, has bounded shrubdepth) if, and only if, from $\mathscr{C}$ one cannot $\mathsf{FO}$-transduce the class of all paths. This establishes one of the three remaining open questions posed by Blumensath and Courcelle about the $\mathsf{MSO}$-transduction quasi-order, even in the stronger form that concerns $\mathsf{FO}$-transductions instead of $\mathsf{MSO}$-transductions. The backbone of our proof is a graph-theoretic statement that says the following: If a graph $G$ excludes a path, the bipartite complement of a path, and a half-graph as semi-induced subgraphs, then the vertex set of $G$ can be partitioned into a bounded number of parts so that every part induces a cograph of bounded height, and every pair of parts semi-induce a bi-cograph of bounded height. This statement may be of independent interest; for instance, it implies that the graphs in question form a class that is linearly $χ$-bounded.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Treelike decompositions for transductions of sparse graphs

We give new decomposition theorems for classes of graphs that can be transduced in first-order logic from classes of sparse graphs -- more precisely, from classes of bounded expansion and from nowhere dense classes. In both cases, the decomposition takes the form of a single colored rooted tree of bounded depth where, in addition, there can be links between nodes that are not related in the tree. The constraint is that the structure formed by the tree and the links has to be sparse. Using the decomposition theorem for transductions of nowhere dense classes, we show that they admit low-shrubdepth covers of size $O(n^\varepsilon)$, where $n$ is the vertex count and $\varepsilon>0$ is any fixed~real. This solves an open problem posed by Gajarský et al. (ACM TOCL '20) and also by Briański et al. (SIDMA '21).

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Twin-width and types

We study problems connected to first-order logic in graphs of bounded twin-width. Inspired by the approach of Bonnet et al. [FOCS 2020], we introduce a robust methodology of local types and describe their behavior in contraction sequences -- the decomposition notion underlying twin-width. We showcase the applicability of the methodology by proving the following two algorithmic results. In both statements, we fix a first-order formula $φ(x_1,\ldots,x_k)$ and a constant $d$, and we assume that on input we are given a graph $G$ together with a contraction sequence of width at most $d$. (A) One can in time $O(n)$ construct a data structure that can answer the following queries in time $O(\log \log n)$: given $w_1,\ldots,w_k$, decide whether $ϕ(w_1,\ldots,w_k)$ holds in $G$. (B) After $O(n)$-time preprocessing, one can enumerate all tuples $w_1,\ldots,w_k$ that satisfy $ϕ(x_1,\ldots,x_k)$ in $G$ with $O(1)$ delay. In the case of (A), the query time can be reduced to $O(1/\varepsilon)$ at the expense of increasing the construction time to $O(n^{1+\varepsilon})$, for any fixed $\varepsilon>0$. Finally, we also apply our tools to prove the following statement, which shows optimal bounds on the VC density of set systems that are first-order definable in graphs of bounded twin-width. (C) Let $G$ be a graph of twin-width $d$, $A$ be a subset of vertices of $G$, and $φ(x_1,\ldots,x_k,y_1,\ldots,y_l)$ be a first-order formula. Then the number of different subsets of $A^k$ definable by $ϕ$ using $l$-tuples of vertices from $G$ as parameters, is bounded by $O(|A|^l)$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Clustering powers of sparse graphs

We prove that if $G$ is a sparse graph --- it belongs to a fixed class of bounded expansion $\mathcal{C}$ --- and $d\in \mathbb{N}$ is fixed, then the $d$th power of $G$ can be partitioned into cliques so that contracting each of these clique to a single vertex again yields a sparse graph. This result has several graph-theoretic and algorithmic consequences for powers of sparse graphs, including bounds on their subchromatic number and efficient approximation algorithms for the chromatic number and the clique number.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Covering minimal separators and potential maximal cliques in $P_t$-free graphs

A graph is called $P_t$-free} if it does not contain a $t$-vertex path as an induced subgraph. While $P_4$-free graphs are exactly cographs, the structure of $P_t$-free graphs for $t \geq 5$ remains little understood. On one hand, classic computational problems such as Maximum Weight Independent Set (MWIS) and $3$-Coloring are not known to be NP-hard on $P_t$-free graphs for any fixed $t$. On the other hand, despite significant effort, polynomial-time algorithms for MWIS in $P_6$-free graphs~[SODA 2019] and $3$-Coloring in $P_7$-free graphs~[Combinatorica 2018] have been found only recently. In both cases, the algorithms rely on deep structural insights into the considered graph classes. One of the main tools in the algorithms for MWIS in $P_5$-free graphs~[SODA 2014] and in $P_6$-free graphs~[SODA 2019] is the so-called Separator Covering Lemma that asserts that every minimal separator in the graph can be covered by the union of neighborhoods of a constant number of vertices. In this note we show that such a statement generalizes to $P_7$-free graphs and is false in $P_8$-free graphs. We also discuss analogues of such a statement for covering potential maximal cliques with unions of neighborhoods.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles

We present a data structure that in a dynamic graph of treedepth at most $d$, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case update time $2^{{\cal O}(d^2)}$, which matches the best known parameter dependency in the running time of a static fpt algorithm for computing the treedepth of a graph. This improves a result of Dvořák et al. [ESA 2014], who for the same problem achieved update time $f(d)$ for some non-elementary (i.e. tower-exponential) function $f$. As a by-product, we improve known upper bounds on the sizes of minimal obstructions for having treedepth $d$ from doubly-exponential in $d$ to $d^{{\cal O}(d)}$. As applications, we design new fully dynamic parameterized data structures for detecting long paths and cycles in general graphs. More precisely, for a fixed parameter $k$ and a dynamic graph $G$, modified over time by edge insertions and deletions, our data structures maintain answers to the following queries: - Does $G$ contain a simple path on $k$ vertices? - Does $G$ contain a simple cycle on at least $k$ vertices? In the first case, the data structure achieves amortized update time $2^{{\cal O}(k^2)}$. In the second case, the amortized update time is $2^{{\cal O}(k^4)} + {\cal O}(k \log n)$. In both cases we assume access to a dictionary on the edges of $G$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Enumerating minimal dominating sets in $K_t$-free graphs and variants

It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we investigate this problem in graph classes defined by forbidding an induced subgraph. In particular, we provide output-polynomial time algorithms for $K_t$-free graphs and variants. This answers a question of Kanté et al. about enumeration in bipartite graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finding large $H$-colorable subgraphs in hereditary graph classes

We study the \textsc{Max Partial $H$-Coloring} problem: given a graph $G$, find the largest induced subgraph of $G$ that admits a homomorphism into $H$, where $H$ is a fixed pattern graph without loops. Note that when $H$ is a complete graph on $k$ vertices, the problem reduces to finding the largest induced $k$-colorable subgraph, which for $k=2$ is equivalent (by complementation) to \textsc{Odd Cycle Transversal}. We prove that for every fixed pattern graph $H$ without loops, \textsc{Max Partial $H$-Coloring} can be solved: $\bullet$ in $\{P_5,F\}$-free graphs in polynomial time, whenever $F$ is a threshold graph; $\bullet$ in $\{P_5,\textrm{bull}\}$-free graphs in polynomial time; $\bullet$ in $P_5$-free graphs in time $n^{\mathcal{O}(ω(G))}$; $\bullet$ in $\{P_6,\textrm{1-subdivided claw}\}$-free graphs in time $n^{\mathcal{O}(ω(G)^3)}$. Here, $n$ is the number of vertices of the input graph $G$ and $ω(G)$ is the maximum size of a clique in~$G$. Furthermore, combining the mentioned algorithms for $P_5$-free and for $\{P_6,\textrm{1-subdivided claw}\}$-free graphs with a simple branching procedure, we obtain subexponential-time algorithms for \textsc{Max Partial $H$-Coloring} in these classes of graphs. Finally, we show that even a restricted variant of \textsc{Max Partial $H$-Coloring} is $\mathsf{NP}$-hard in the considered subclasses of $P_5$-free graphs, if we allow loops on $H$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Graphs of bounded cliquewidth are polynomially $χ$-bounded

We prove that if $\mathcal{C}$ is a hereditary class of graphs that is polynomially $χ$-bounded, then the class of graphs that admit decompositions into pieces belonging to $\mathcal{C}$ along cuts of bounded rank is also polynomially $χ$-bounded. In particular, this implies that for every positive integer $k$, the class of graphs of cliquewidth at most $k$ is polynomially $χ$-bounded.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space

For many algorithmic problems on graphs of treewidth $t$, a standard dynamic programming approach gives an algorithm with time and space complexity $2^{\mathcal{O}(t)}\cdot n^{\mathcal{O}(1)}$. It turns out that when one considers the more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the space complexity to polynomial, while retaining time complexity of the form $2^{\mathcal{O}(d)}\cdot n^{\mathcal{O}(1)}$, where $d$ is the treedepth. This transfer of methodology is, however, far from automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with time and space complexity $2^{\mathcal{O}(t\log t)}\cdot n^{\mathcal{O}(1)}$ on graphs of treewidth $t$, but it is not clear how to convert them into time-efficient polynomial space algorithms for graphs of low treedepth. Cygan et al. (FOCS'11) introduced the Cut&Count technique and showed that a certain class of problems with connectivity constraints can be solved in time and space complexity $2^{\mathcal{O}(t)}\cdot n^{\mathcal{O}(1)}$. Recently, Hegerfeld and Kratsch (STACS'20) showed that, for some of those problems, the Cut&Count technique can be also applied in the setting of treedepth, and it gives algorithms with running time $2^{\mathcal{O}(d)}\cdot n^{\mathcal{O}(1)}$ and polynomial space usage. However, a number of important problems eluded such a treatment, with the most prominent examples being Hamiltonian Cycle and Longest Path. In this paper we clarify the situation by showing that Hamiltonian Cycle, Hamiltonian Path, Long Cycle, Long Path, and Min Cycle Cover all admit $5^d\cdot n^{\mathcal{O}(1)}$-time and polynomial space algorithms on graphs of treedepth $d$. The algorithms are randomized Monte Carlo with only false negatives.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On polynomial recursive sequences

We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the study of nonlinear extensions of weighted automata, where (non)expressiveness results translate to class separations. A typical example of a polynomial recursive sequence is b_n=n!. Our main result is that the sequence u_n=n^n is not polynomial recursive.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the effect of symmetry requirement for rendezvous on the complete graph

We consider a classic rendezvous game where two players try to meet each other on a set of $n$ locations. In each round, every player visits one of the locations and the game finishes when the players meet at the same location. The goal is to devise strategies for both players that minimize the expected waiting time till the rendezvous. In the asymmetric case, when the strategies of the players may differ, it is known that the optimum expected waiting time of $\frac{n+1}{2}$ is achieved by the wait-for-mommy pair of strategies, where one of the players stays at one location for $n$ rounds, while the other player searches through all the $n$ locations in a random order. However, if we insist that the players are symmetric --- they are expected to follow the same strategy --- then the best known strategy, proposed by Anderson and Weber, achieves an asymptotic expected waiting time of $0.829 n$. We show that the symmetry requirement indeed implies that the expected waiting time needs to be asymptotically larger than in the asymmetric case. Precisely, we prove that for every $n\geqslant 2$, if the players need to employ the same strategy, then the expected waiting time is at least $\frac{n+1}{2}+\varepsilon n$, where $\varepsilon=2^{-36}$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five

A hole in a graph is an induced cycle of length at least $4$, and an antihole is the complement of an induced cycle of length at least $4$. A hole or antihole is long if its length is at least $5$. For an integer $k$, the $k$-prism is the graph consisting of two cliques of size $k$ joined by a matching. The complexity of Maximum (Weight) Independent Set (MWIS) in long-hole-free graphs remains an important open problem. In this paper we give a polynomial time algorithm to solve MWIS in long-hole-free graphs with no $k$-prism (for any fixed integer $k$), and a subexponential algorithm for MWIS in long-hole-free graphs in general. As a special case this gives a polynomial time algorithm to find a maximum weight clique in perfect graphs with no long antihole, and no hole of length $6$. The algorithms use the framework of minimal chordal completions and potential maximal cliques.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Polynomial-time algorithm for Maximum Weight Independent Set on $P_6$-free graphs

In the classic Maximum Weight Independent Set problem we are given a graph $G$ with a nonnegative weight function on vertices, and the goal is to find an independent set in $G$ of maximum possible weight. While the problem is NP-hard in general, we give a polynomial-time algorithm working on any $P_6$-free graph, that is, a graph that has no path on $6$ vertices as an induced subgraph. This improves the polynomial-time algorithm on $P_5$-free graphs of Lokshtanov et al. (SODA 2014), and the quasipolynomial-time algorithm on $P_6$-free graphs of Lokshtanov et al (SODA 2016). The main technical contribution leading to our main result is enumeration of a polynomial-size family $\mathcal{F}$ of vertex subsets with the following property: for every maximal independent set $I$ in the graph, $\mathcal{F}$ contains all maximal cliques of some minimal chordal completion of $G$ that does not add any edge incident to a vertex of $I$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The monitoring problem for timed automata

We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so under a different perspective, that is, we consider a dynamic version of the problem, called monitoring problem, where the automaton is fixed and the input is revealed as in a stream, one symbol at a time following the natural order on positions. The goal here is to design a dynamic data structure that can be queried about whether the word consisting of symbols revealed so far is accepted by the automaton, and that can be efficiently updated when the next symbol is revealed. We provide complexity bounds for this monitoring problem, by considering timed automata that process symbols interleaved with timestamps. The main contribution is that monitoring of a one-clock timed automaton, with all its components but the clock constants fixed, can be done in amortised constant time per input symbol.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

VC density of set systems defnable in tree-like graphs

We study set systems definable in graphs using variants of logic with different expressive power. Our focus is on the notion of Vapnik-Chervonenkis density: the smallest possible degree of a polynomial bounding the cardinalities of restrictions of such set systems. On one hand, we prove that if $φ(\bar x,\bar y)$ is a fixed CMSO$_1$ formula and $\cal C$ is a class of graphs with uniformly bounded cliquewidth, then the set systems defined by $φ$ in graphs from $\cal C$ have VC density at most $|\bar y|$, which is the smallest bound that one could expect. We also show an analogous statement for the case when $φ(\bar x,\bar y)$ is a CMSO$_2$ formula and $\cal C$ is a class of graphs with uniformly bounded treewidth. We complement these results by showing that if $\cal C$ has unbounded cliquewidth (respectively, treewidth), then, under some mild technical assumptions on $\cal C$, the set systems definable by CMSO$_1$ (respectively, CMSO$_2$) formulas in graphs from $\cal C$ may have unbounded VC dimension, hence also unbounded VC density.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A subexponential parameterized algorithm for Proper Interval Completion

In the Proper Interval Completion problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into a proper interval graph, i.e., a graph admitting an intersection model of equal-length intervals on a line. The study of Proper Interval Completion from the viewpoint of parameterized complexity has been initiated by Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999], who showed an algorithm for the problem working in $O(16^k (n + m))$ time. In this paper we present an algorithm with running time $k^{O(k^{2/3})} + O(nm(kn + m))$, which is the first subexponential parameterized algorithm for Proper Interval Completion.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Exploring Subexponential Parameterized Complexity of Completion Problems

Let ${\cal F}$ be a family of graphs. In the ${\cal F}$-Completion problem, we are given a graph $G$ and an integer $k$ as input, and asked whether at most $k$ edges can be added to $G$ so that the resulting graph does not contain a graph from ${\cal F}$ as an induced subgraph. It appeared recently that special cases of ${\cal F}$-Completion, the problem of completing into a chordal graph known as Minimum Fill-in, corresponding to the case of ${\cal F}=\{C_4,C_5,C_6,\ldots\}$, and the problem of completing into a split graph, i.e., the case of ${\cal F}=\{C_4, 2K_2, C_5\}$, are solvable in parameterized subexponential time $2^{O(\sqrt{k}\log{k})}n^{O(1)}$. The exploration of this phenomenon is the main motivation for our research on ${\cal F}$-Completion. In this paper we prove that completions into several well studied classes of graphs without long induced cycles also admit parameterized subexponential time algorithms by showing that: - The problem Trivially Perfect Completion is solvable in parameterized subexponential time $2^{O(\sqrt{k}\log{k})}n^{O(1)}$, that is ${\cal F}$-Completion for ${\cal F} =\{C_4, P_4\}$, a cycle and a path on four vertices. - The problems known in the literature as Pseudosplit Completion, the case where ${\cal F} = \{2K_2, C_4\}$, and Threshold Completion, where ${\cal F} = \{2K_2, P_4, C_4\}$, are also solvable in time $2^{O(\sqrt{k}\log{k})} n^{O(1)}$. We complement our algorithms for ${\cal F}$-Completion with the following lower bounds: - For ${\cal F} = \{2K_2\}$, ${\cal F} = \{C_4\}$, ${\cal F} = \{P_4\}$, and ${\cal F} = \{2K_2, P_4\}$, ${\cal F}$-Completion cannot be solved in time $2^{o(k)} n^{O(1)}$ unless the Exponential Time Hypothesis (ETH) fails. Our upper and lower bounds provide a complete picture of the subexponential parameterized complexity of ${\cal F}$-Completion problems for ${\cal F}\subseteq\{2K_2, C_4, P_4\}$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Minimum Bisection is fixed parameter tractable

In the classic Minimum Bisection problem we are given as input a graph $G$ and an integer $k$. The task is to determine whether there is a partition of $V(G)$ into two parts $A$ and $B$ such that $||A|-|B|| \leq 1$ and there are at most $k$ edges with one endpoint in $A$ and the other in $B$. In this paper we give an algorithm for Minimum Bisection with running time $O(2^{O(k^{3})}n^3 \log^3 n)$. This is the first fixed parameter tractable algorithm for Minimum Bisection. At the core of our algorithm lies a new decomposition theorem that states that every graph $G$ can be decomposed by small separators into parts where each part is "highly connected" in the following sense: any cut of bounded size can separate only a limited number of vertices from each part of the decomposition. Our techniques generalize to the weighted setting, where we seek for a bisection of minimum weight among solutions that contain at most $k$ edges.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A O(c^k n) 5-Approximation Algorithm for Treewidth

We give an algorithm that for an input n-vertex graph G and integer k>0, in time 2^[O(k)]n either outputs that the treewidth of G is larger than k, or gives a tree decomposition of G of width at most 5k+4. This is the first algorithm providing a constant factor approximation for treewidth which runs in time single-exponential in k and linear in n. Treewidth based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single-exponential in the treewidth and linear in the input size.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)

Given two graphs $H$ and $G$, the Subgraph Isomorphism problem asks if $H$ is isomorphic to a subgraph of $G$. While NP-hard in general, algorithms exist for various parameterized versions of the problem: for example, the problem can be solved (1) in time $2^{O(|V(H)|)}\cdot n^{O(\tw(H))}$ using the color-coding technique of Alon, Yuster, and Zwick; (2) in time $f(|V(H)|,\tw(G))\cdot n$ using Courcelle's Theorem; (3) in time $f(|V(H)|,\genus(G))\cdot n$ using a result on first-order model checking by Frick and Grohe; or (4) in time $f(\maxdeg(H))\cdot n^{O(\tw(G)})$ for connected $H$ using the algorithm of Matoušek and Thomas. Already this small sample of results shows that the way an algorithm can depend on the parameters is highly nontrivial and subtle. We develop a framework involving 10 relevant parameters for each of $H$ and $G$ (such as treewidth, pathwidth, genus, maximum degree, number of vertices, number of components, etc.), and ask if an algorithm with running time \[ f_1(p_1,p_2,..., p_\ell)\cdot n^{f_2(p_{\ell+1},..., p_k)} \] exist, where each of $p_1,..., p_k$ is one of the 10 parameters depending only on $H$ or $G$. We show that {\em all} the questions arising in this framework are answered by a set of 11 maximal positive results (algorithms) and a set of 17 maximal negative results (hardness proofs); some of these results already appear in the literature, while others are new in this paper. On the algorithmic side, our study reveals for example that an unexpected combination of bounded degree, genus, and feedback vertex set number of $G$ gives rise to a highly nontrivial algorithm for Subgraph Isomorphism. On the hardness side, we present W[1]-hardness proofs under extremely restricted conditions, such as when $H$ is a bounded-degree tree of constant pathwidth and $G$ is a planar graph of bounded pathwidth.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Minimizing Rosenthal Potential in Multicast Games

A multicast game is a network design game modelling how selfish non-cooperative agents build and maintain one-to-many network communication. There is a special source node and a collection of agents located at corresponding terminals. Each agent is interested in selecting a route from the special source to its terminal minimizing the cost. The mutual influence of the agents is determined by a cost sharing mechanism, which evenly splits the cost of an edge among all the agents using it for routing. In this paper we provide several algorithmic and complexity results on finding a Nash equilibrium minimizing the value of Rosenthal potential. Let n be the number of agents and G be the communication network. We show that - For a given strategy profile s and integer k>=1, there is a local search algorithm which in time n^{O(k)}|G|^{O(1)} finds a better strategy profile, if there is any, in a k-exchange neighbourhood of s. In other words, the algorithm decides if Rosenthal potential can be decreased by changing strategies of at most k agents; - The running time of our local search algorithm is essentially tight: unless FPT= W[1], for any function f(k), searching of the k-neighbourhood cannot be done in time f(k)|G|^{O(1)}. The key ingredient of our algorithmic result is a subroutine that finds an equilibrium with minimum potential in 3^n|G|^{O(1)} time. In other words, finding an equilibrium with minimum potential is fixed-parameter tractable when parameterized by the number of agents.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph

Cutwidth of a digraph is a width measure introduced by Chudnovsky, Fradkin, and Seymour [4] in connection with development of a structural theory for tournaments, or more generally, for semi-complete digraphs. In this paper we provide an algorithm with running time 2^{O(\sqrt{k log k})} * n^{O(1)} that tests whether the cutwidth of a given n-vertex semi-complete digraph is at most k, improving upon the currently fastest algorithm of the second author [18] that works in 2^{O(k)} * n^2 time. As a byproduct, we obtain a new algorithm for Feedback Arc Set in tournaments (FAST) with running time 2^{c\sqrt{k}} * n^{O(1)}, where c = 2π/ \sqrt(3)*\ln(2) <= 5.24, that is simpler than the algorithms of Feige [9] and of Karpinski and Schudy[16], both also working in 2^{O(\sqrt{k})} * n^{O(1)} time. Our techniques can be applied also to other layout problems on semi-complete digraphs. We show that the Optimal Linear Arrangement problem, a close relative of Feedback Arc Set, can be solved in 2^{O(k^{1/3} \sqrt{\log k})} * n^{O(1)} time, where k is the target cost of the ordering.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable

Given a graph G and k pairs of vertices (s_1,t_1), ..., (s_k,t_k), the k-Vertex-Disjoint Paths problem asks for pairwise vertex-disjoint paths P_1, ..., P_k such that P_i goes from s_i to t_i. Schrijver [SICOMP&#39;94] proved that the k-Vertex-Disjoint Paths problem on planar directed graphs can be solved in time n^{O(k)}. We give an algorithm with running time 2^{2^{O(k^2)}} n^{O(1)} for the problem, that is, we show the fixed-parameter tractability of the problem.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings

The notions of cutwidth and pathwidth of digraphs play a central role in the containment theory for tournaments, or more generally semi-complete digraphs, developed in a recent series of papers by Chudnovsky, Fradkin, Kim, Scott, and Seymour [2, 3, 4, 8, 9, 11]. In this work we introduce a new approach to computing these width measures on semi-complete digraphs, via degree orderings. Using the new technique we are able to reprove the main results of [2, 9] in a unified and significantly simplified way, as well as obtain new results. First, we present polynomial-time approximation algorithms for both cutwidth and pathwidth, faster and simpler than the previously known ones; the most significant improvement is in case of pathwidth, where instead of previously known O(OPT)-approximation in fixed-parameter tractable time [6] we obtain a constant-factor approximation in polynomial time. Secondly, by exploiting the new set of obstacles for cutwidth and pathwidth, we show that topological containment and immersion in semi-complete digraphs can be tested in single-exponential fixed-parameter tractable time. Finally, we present how the new approach can be used to obtain exact fixed-parameter tractable algorithms for cutwidth and pathwidth, with single- exponential running time dependency on the optimal width.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Finding a maximum induced degenerate subgraph faster than 2^n

In this paper we study the problem of finding a maximum induced d-degenerate subgraph in a given n-vertex graph from the point of view of exact algorithms. We show that for any fixed d one can find a maximum induced d-degenerate subgraph in randomized (2-eps_d)^n n^O(1) time, for some constant eps_d>0 depending only on d. Moreover, our algorithm can be used to sample inclusion-wise maximal induced d-degenerate subgraphs in such a manner that every such subgraph is output with probability at least (2-eps_d)^-n; hence, we prove that their number is bounded by (2-eps_d)^n.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Fixed-parameter tractability of multicut in directed acyclic graphs

The MULTICUT problem, given a graph G, a set of terminal pairs T={(s_i,t_i) | 1 <= i <= r} and an integer p, asks whether one can find a cutset consisting of at most p non-terminal vertices that separates all the terminal pairs, i.e., after removing the cutset, t_i is not reachable from s_i for each 1 <= i <= r. The fixed-parameter tractability of MULTICUT in undirected graphs, parameterized by the size of the cutset only, has been recently proven by Marx and Razgon (STOC&#39;11) and, independently, by Bousquet et al. (STOC&#39;11), after resisting attacks as a long-standing open problem. In this paper we prove that MULTICUT is fixed-parameter tractable on directed acyclic graphs, when parameterized both by the size of the cutset and the number of terminal pairs. We complement this result by showing that this is implausible for parameterization by the size of the cutset only, as this version of the problem remains W[1]-hard.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Known algorithms for EDGE CLIQUE COVER are probably optimal

In the EDGE CLIQUE COVER (ECC) problem, given a graph G and an integer k, we ask whether the edges of G can be covered with k complete subgraphs of G or, equivalently, whether G admits an intersection model on k-element universe. Gramm et al. [JEA 2008] have shown a set of simple rules that reduce the number of vertices of G to 2^k, and no algorithm is known with significantly better running time bound than a brute-force search on this reduced instance. In this paper we show that the approach of Gramm et al. is essentially optimal: we present a polynomial time algorithm that reduces an arbitrary 3-CNF-SAT formula with n variables and m clauses to an equivalent ECC instance (G,k) with k = O(log n) and |V(G)| = O(n + m). Consequently, there is no 2^{2^{o(k)}}poly(n) time algorithm for the ECC problem, unless the Exponential Time Hypothesis fails. To the best of our knowledge, these are the first results for a natural, fixed-parameter tractable problem, and proving that a doubly-exponential dependency on the parameter is essentially necessary.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Scheduling partially ordered jobs faster than 2^n

In the SCHED problem we are given a set of n jobs, together with their processing times and precedence constraints. The task is to order the jobs so that their total completion time is minimized. SCHED is a special case of the Traveling Repairman Problem with precedences. A natural dynamic programming algorithm solves both these problems in 2^n n^O(1) time, and whether there exists an algorithms solving SCHED in O(c^n) time for some constant c < 2 was an open problem posted in 2004 by Woeginger. In this paper we answer this question positively.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Sitting closer to friends than enemies, revisited

Signed graphs, i.e., undirected graphs with edges labelled with a plus or minus sign, are commonly used to model relationships in social networks. Recently, Kermarrec and Thraves initiated the study of the problem of appropriately visualising the network: They asked whether any signed graph can be embedded into the metric space R^l in such a manner that every vertex is closer to all its friends (neighbours via positive edges) than to all its enemies (neighbours via negative edges). Interestingly, embeddability into R^1 can be expressed as a purely combinatorial problem. In this paper we pursue a deeper study of this particular case, answering several questions posed by Kermarrec and Thraves. First, we refine the approach of Kermarrec and Thraves for the case of complete signed graphs by showing that the problem is closely related to the recognition of proper interval graphs. Second, we prove that the general case, whose polynomial-time tractability remained open, is in fact NP-complete. Finally, we provide lower and upper bounds for the time complexity of the general case: we prove that the existence of a subexponential time (in the number of vertices and edges of the input signed graph) algorithm would violate the Exponential Time Hypothesis, whereas a simple dynamic programming approach gives a running time single-exponential in the number of vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Clique cover and graph separation: New incompressibility results

The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework of parameterized complexity. Although a framework for proving kernelization lower bounds has been discovered in 2008 and successfully applied multiple times over the last three years, establishing kernelization complexity of many important problems remains open. In this paper we show that, unless NP is a subset of coNP/poly and the polynomial hierarchy collapses up to its third level, the following parameterized problems do not admit a polynomial-time preprocessing algorithm that reduces the size of an instance to polynomial in the parameter: - EDGE CLIQUE COVER, parameterized by the number of cliques, - DIRECTED EDGE/VERTEX MULTIWAY CUT, parameterized by the size of the cutset, even in the case of two terminals, - EDGE/VERTEX MULTICUT, parameterized by the size of the cutset, and - k-WAY CUT, parameterized by the size of the cutset. The existence of a polynomial kernelization for EDGE CLIQUE COVER was a seasoned veteran in open problem sessions. Furthermore, our results complement very recent developments in designing parameterized algorithms for cut problems by Marx and Razgon [STOC&#39;11], Bousquet et al. [STOC&#39;11], Kawarabayashi and Thorup [FOCS&#39;11] and Chitnis et al. [SODA&#39;12].

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On group feedback vertex set parameterized by the size of the cutset

We study the parameterized complexity of a robust generalization of the classical Feedback Vertex Set problem, namely the Group Feedback Vertex Set problem; we are given a graph G with edges labeled with group elements, and the goal is to compute the smallest set of vertices that hits all cycles of G that evaluate to a non-null element of the group. This problem generalizes not only Feedback Vertex Set, but also Subset Feedback Vertex Set, Multiway Cut and Odd Cycle Transversal. Completing the results of Guillemot [Discr. Opt. 2011], we provide a fixed-parameter algorithm for the parameterization by the size of the cutset only. Our algorithm works even if the group is given as a polynomial-time oracle.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On Multiway Cut parameterized above lower bounds

In this paper we consider two above lower bound parameterizations of the Node Multiway Cut problem - above the maximum separating cut and above a natural LP-relaxation - and prove them to be fixed-parameter tractable. Our results imply O*(4^k) algorithms for Vertex Cover above Maximum Matching and Almost 2-SAT as well as an O*(2^k) algorithm for Node Multiway Cut with a standard parameterization by the solution size, improving previous bounds for these problems.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Problems parameterized by treewidth tractable in single exponential time: a logical approach

We introduce a variant of modal logic, dubbed EXISTENTIAL COUNTING MODAL LOGIC (ECML), which captures a vast majority of problems known to be tractable in single exponential time when parameterized by treewidth. It appears that all these results can be subsumed by the theorem that model checking of ECML admits an algorithm with such complexity. We extend ECML by adding connectivity requirements and, using the Cut&Count technique introduced by Cygan et al. [4], prove that problems expressible in the extension are also tractable in single exponential time when parameterized by treewidth; however, using randomization. The need for navigationality of the introduced logic is justified by a negative result that two expository problems involving non-acyclic conditions, C_l VERTEX DELETION and GIRTH>l VERTEX DELETION for l>=5, do not admit such a robust algorithm unless Exponential Time Hypothesis fails.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Solving connectivity problems parameterized by treewidth in single exponential time

For the vast majority of local graph problems standard dynamic programming techniques give c^tw V^O(1) algorithms, where tw is the treewidth of the input graph. On the other hand, for problems with a global requirement (usually connectivity) the best-known algorithms were naive dynamic programming schemes running in tw^O(tw) V^O(1) time. We breach this gap by introducing a technique we dubbed Cut&Count that allows to produce c^tw V^O(1) Monte Carlo algorithms for most connectivity-type problems, including Hamiltonian Path, Feedback Vertex Set and Connected Dominating Set, consequently answering the question raised by Lokshtanov, Marx and Saurabh [SODA&#39;11] in a surprising way. We also show that (under reasonable complexity assumptions) the gap cannot be breached for some problems for which Cut&Count does not work, like CYCLE PACKING. The constant c we obtain is in all cases small (at most 4 for undirected problems and at most 6 for directed ones), and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. Our results have numerous consequences in various fields, like FPT algorithms, exact and approximate algorithms on planar and H-minor-free graphs and algorithms on graphs of bounded degree. In all these fields we are able to improve the best-known results for some problems.

0 citations0 reviewsNo code linkedOpen access