Dimitrios M. Thilikos

A linear fixed parameter tractable algorithm for connected pathwidth

The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search where we are given a system of tunnels that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one. Two desired characteristics for a cleaning strategy is to be monotone (no recontamination occurs) and connected (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called {\em connected pathwidth}. We prove that connected pathwidth is fixed parameter tractable, in particular we design a $2^{O(k^2)}\cdot n$ time algorithm that checks whether the connected pathwidth of $G$ is at most $k.$ This resolves an open question by [Dereniowski, Osula, and Rz{ą}{ż}ewski, Finding small-width connected path-decompositions in polynomial time. Theor. Comput. Sci., 794:85-100, 2019]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced in [Bodlaender and Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358-402, 1996] for the design of linear parameterized algorithms for treewidth and pathwidth. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted so to deliver linear parameterized algorithms for the connected variants of other width parameters as well.

Combing a Linkage in an Annulus

A linkage in a graph $G$ of size $k$ is a subgraph $L$ of $G$ whose connected components are $k$ paths. The pattern of a linkage of size $k$ is the set of $k$ pairs formed by the endpoints of these paths. A consequence of the Unique Linkage Theorem is the following: there exists a function $f:\mathbb{N}\to\mathbb{N}$ such that if a plane graph $G$ contains a sequence $\mathcal{C}$ of at least $f(k)$ nested cycles and a linkage of size at most $k$ whose pattern vertices lay outside the outer cycle of $\mathcal{C},$ then $G$ contains a linkage with the same pattern avoiding the inner cycle of $\mathcal{C}$ . In this paper we prove the following variant of this result: Assume that all the cycles in $\mathcal{C}$ are "orthogonally" traversed by a linkage $P$ and $L$ is a linkage whose pattern vertices may lay either outside the outer cycle or inside the inner cycle of $\mathcal{C}:=[C_{1},\ldots,C_{p},\ldots,C_{2p-1}]$ . We prove that there are two functions $g,f:\mathbb{N}\to\mathbb{N}$ , such that if $L$ has size at most $k$ , $P$ has size at least $f(k),$ and $|\mathcal{C}|\geq g(k)$ , then there is a linkage with the same pattern as $L$ that is "internally combed" by $P$ , in the sense that $L\cap C_{p}\subseteq P\cap C_{p}$ . In fact, we prove this result in the most general version where the linkage $L$ is $s$ -scattered: no two vertices of distinct paths of $L$ are within distance at most $s$ . We deduce several variants of this result in the cases where $s=0$ and $s>0$ . These variants permit the application of the unique linkage theorem on several path routing problems on embedded graphs.

Contraction Bidimensionality of Geometric Intersection Graphs

Given a graph $G$ , we define ${\bf bcg}(G)$ as the minimum $k$ for which $G$ can be contracted to the uniformly triangulated grid $Γ_{k}$ . A graph class ${\cal G}$ has the SQG ${\bf C}$ property if every graph $G\in{\cal G}$ has treewidth $\mathcal{O}({\bf bcg}(G)^{c})$ for some $1\leq c<2$ . The SQG ${\bf C}$ property is important for algorithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a wide family of graph classes that satisfy the SQG ${\bf C}$ property. This family includes, in particular, bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for contraction bidimensional problems.

Hcore-Init: Neural Network Initialization based on Graph Degeneracy

Neural networks are the pinnacle of Artificial Intelligence, as in recent years we witnessed many novel architectures, learning and optimization techniques for deep learning. Capitalizing on the fact that neural networks inherently constitute multipartite graphs among neuron layers, we aim to analyze directly their structure to extract meaningful information that can improve the learning process. To our knowledge graph mining techniques for enhancing learning in neural networks have not been thoroughly investigated. In this paper we propose an adapted version of the k-core structure for the complete weighted multipartite graph extracted from a deep learning architecture. As a multipartite graph is a combination of bipartite graphs, that are in turn the incidence graphs of hypergraphs, we design k-hypercore decomposition, the hypergraph analogue of k-core degeneracy. We applied k-hypercore to several neural network architectures, more specifically to convolutional neural networks and multilayer perceptrons for image recognition tasks after a very short pretraining. Then we used the information provided by the hypercore numbers of the neurons to re-initialize the weights of the neural network, thus biasing the gradient optimization scheme. Extensive experiments proved that k-hypercore outperforms the state-of-the-art initialization methods.

Minor-Obstructions for Apex-Pseudoforests

A graph is called a pseudoforest if none of its connected components contains more than one cycle. A graph is an apex-pseudoforest if it can become a pseudoforest by removing one of its vertices. We identify 33 graphs that form the minor-obstruction set of the class of apex-pseudoforests, i.e., the set of all minor-minimal graphs that are not apex-pseudoforests.

preprint2021arXiv

Block Elimination Distance

We introduce the block elimination distance as a measure of how close a graph is to some particular graph class. Formally, given a graph class ${\cal G}$ , the class ${\cal B}({\cal G})$ contains all graphs whose blocks belong to ${\cal G}$ and the class ${\cal A}({\cal G})$ contains all graphs where the removal of a vertex creates a graph in ${\cal G}$ . Given a hereditary graph class ${\cal G}$ , we recursively define ${\cal G}^{(k)}$ so that ${\cal G}^{(0)}={\cal B}({\cal G})$ and, if $k\geq 1$ , ${\cal G}^{(k)}={\cal B}({\cal A}({\cal G}^{(k-1)}))$ . The block elimination distance of a graph $G$ to a graph class ${\cal G}$ is the minimum $k$ such that $G\in{\cal G}^{(k)}$ and can be seen as an analog of the elimination distance parameter, with the difference that connectivity is now replaced by biconnectivity. We show that, for every non-trivial hereditary class ${\cal G}$ , the problem of deciding whether $G\in{\cal G}^{(k)}$ is NP-complete. We focus on the case where ${\cal G}$ is minor-closed and we study the minor obstruction set of ${\cal G}^{(k)}$ . We prove that the size of the obstructions of ${\cal G}^{(k)}$ is upper bounded by some explicit function of $k$ and the maximum size of a minor obstruction of ${\cal G}$ . This implies that the problem of deciding whether $G\in{\cal G}^{(k)}$ is constructively fixed parameter tractable, when parameterized by $k$ . Our results are based on a structural characterization of the obstructions of ${\cal B}({\cal G})$ , relatively to the obstructions of ${\cal G}$ . We give two graph operations that generate members of ${\cal G}^{(k)}$ from members of ${\cal G}^{(k-1)}$ and we prove that this set of operations is complete for the class ${\cal O}$ of outerplanar graphs. This yields the identification of all members ${\cal O}\cap{\cal G}^{(k)}$ , for every $k\in\mathbb{N}$ and every non-trivial minor-closed graph class ${\cal G}$ .

preprint2021arXiv

k-apices of minor-closed graph classes. II. Parameterized algorithms

Let ${\cal G}$ be a minor-closed graph class. We say that a graph $G$ is a $k$ -apex of ${\cal G}$ if $G$ contains a set $S$ of at most $k$ vertices such that $G\setminus S$ belongs to ${\cal G}$ . We denote by ${\cal A}_k ({\cal G})$ the set of all graphs that are $k$ -apices of ${\cal G}.$ In the first paper of this series we obtained upper bounds on the size of the graphs in the minor-obstruction set of ${\cal A}_k ({\cal G})$ , i.e., the minor-minimal set of graphs not belonging to ${\cal A}_k ({\cal G}).$ In this article we provide an algorithm that, given a graph $G$ on $n$ vertices, runs in $2^{{\sf poly}(k)}\cdot n^3$ -time and either returns a set $S$ certifying that $G \in {\cal A}_k ({\cal G})$ , or reports that $G \notin {\cal A}_k ({\cal G})$ . Here ${\sf poly}$ is a polynomial function whose degree depends on the maximum size of a minor-obstruction of ${\cal G}.$ In the special case where ${\cal G}$ excludes some apex graph as a minor, we give an alternative algorithm running in $2^{{\sf poly}(k)}\cdot n^2$ -time.

preprint2020arXiv

Bidimensionality and Kernels

Bidimensionality Theory was introduced by [E.D. Demaine, F.V. Fomin, M.Hajiaghayi, and D.M. Thilikos. Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs, J. ACM, 52 (2005), pp.866--893] as a tool to obtain sub-exponential time parameterized algorithms on H-minor-free graphs. In [E.D. Demaine and M.Hajiaghayi, Bidimensionality: new connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2005, pp.590--601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (respectively contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO), admits a linear kernel for classes of graphs that exclude a fixed graph (respectively an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems g graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work.

preprint2020arXiv

Edge Degeneracy: Algorithmic and Structural Results

We consider a cops and robber game where the cops are blocking edges of a graph, while the robber occupies its vertices. At each round of the game, the cops choose some set of edges to block and right after the robber is obliged to move to another vertex traversing at most $s$ unblocked edges ( $s$ can be seen as the speed of the robber). Both parts have complete knowledge of the opponent's moves and the cops win when they occupy all edges incident to the robbers position. We introduce the capture cost on $G$ against a robber of speed $s$ . This defines a hierarchy of invariants, namely $δ^{1}_{\rm e},δ^{2}_{\rm e},\ldots,δ^{\infty}_{\rm e}$ , where $δ^{\infty}_{\rm e}$ is an edge-analogue of the admissibility graph invariant, namely the {\em edge-admissibility} of a graph. We prove that the problem asking wether $δ^{s}_{\rm e}(G)\leq k$ , is polynomially solvable when $s\in \{1,2,\infty\}$ while, otherwise, it is NP-complete. Our main result is a structural theorem for graphs of bounded edge-admissibility. We prove that every graph of edge-admissibility at most $k$ can be constructed using $(\leq k)$ -edge-sums, starting from graphs whose all vertices, except possibly from one, have degree at most $k$ . Our structural result is approximately tight in the sense that graphs generated by this construction always have edge-admissibility at most $2k-1$ . Our proofs are based on a precise structural characterization of the graphs that do not contain $θ_{r}$ as an immersion, where $θ_{r}$ is the graph on two vertices and $r$ parallel edges.

preprint2020arXiv

Structure and enumeration of K4-minor-free links and link-diagrams

We study the class L of link-types that admit a K4-minor-free diagram, i.e., they can be projected on the plane so that the resulting graph does not contain any subdivision of K4. We prove that L is the closure of a subclass of torus links under the operation of connected sum. Using this structural result, we enumerate L and subclasses of it, with respect to the minimum number of crossings or edges in a projection of L' in L. Further, we obtain counting formulas and asymptotic estimates for the connected K4-minor-free link-diagrams, minimal K4-minor-free link-diagrams, and K4-minor-free diagrams of the unknot.

preprint2018arXiv

Partial complementation of graphs

A partial complement of the graph $G$ is a graph obtained from $G$ by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph $G$ and graph class $\mathcal{G}$ , is there a partial complement of $G$ which is in $\mathcal{G}$ ? We show that this problem can be solved in polynomial time for various choices of the graphs class $\mathcal{G}$ , such as bipartite, degenerate, or cographs. We complement these results by proving that the problem is NP-complete when $\mathcal{G}$ is the class of $r$ -regular graphs.

A k-core Decomposition Framework for Graph Clustering

Graph clustering or community detection constitutes an important task for investigating the internal structure of graphs, with a plethora of applications in several domains. Traditional techniques for graph clustering, such as spectral methods, typically suffer from high time and space complexity. In this article, we present CoreCluster, an efficient graph clustering framework based on the concept of graph degeneracy, that can be used along with any known graph clustering algorithm. Our approach capitalizes on processing the graph in an hierarchical manner provided by its core expansion sequence, an ordered partition of the graph into different levels according to the k-core decomposition. Such a partition provides an efficient way to process the graph in an incremental manner that preserves its clustering structure, while making the execution of the chosen clustering algorithm much faster due to the smaller size of the graph's partitions onto which the algorithm operates. An experimental analysis on a multitude of real and synthetic data demonstrates that our approach can be applied to any clustering algorithm accelerating the clustering process, while the quality of the clustering structure is preserved or even improved.

Explicit linear kernels for packing problems

During the last years, several algorithmic meta-theorems have appeared (Bodlaender et al. [FOCS 2009], Fomin et al. [SODA 2010], Kim et al. [ICALP 2013]) guaranteeing the existence of linear kernels on sparse graphs for problems satisfying some generic conditions. The drawback of such general results is that it is usually not clear how to derive from them constructive kernels with reasonably low explicit constants. To fill this gap, we recently presented [STACS 2014] a framework to obtain explicit linear kernels for some families of problems whose solutions can be certified by a subset of vertices. In this article we enhance our framework to deal with packing problems, that is, problems whose solutions can be certified by collections of subgraphs of the input graph satisfying certain properties. ${\mathcal F}$ -Packing is a typical example: for a family ${\mathcal F}$ of connected graphs that we assume to contain at least one planar graph, the task is to decide whether a graph $G$ contains $k$ vertex-disjoint subgraphs such that each of them contains a graph in ${\mathcal F}$ as a minor. We provide explicit linear kernels on sparse graphs for the following two orthogonal generalizations of ${\mathcal F}$ -Packing: for an integer $\ell \geq 1$ , one aims at finding either minor-models that are pairwise at distance at least $\ell$ in $G$ ( $\ell$ - ${\mathcal F}$ -Packing), or such that each vertex in $G$ belongs to at most $\ell$ minors-models ( ${\mathcal F}$ -Packing with $\ell$ -Membership). Finally, we also provide linear kernels for the versions of these problems where one wants to pack subgraphs instead of minors.

Irrelevant Vertices for the Planar Disjoint Paths Problem

The Disjoint Paths Problem asks, given a graph $G$ and a set of pairs of terminals $(s_{1},t_{1}),\ldots,(s_{k},t_{k})$ , whether there is a collection of $k$ pairwise vertex-disjoint paths linking $s_{i}$ and $t_{i}$ , for $i=1,\ldots,k.$ In their $f(k)\cdot n^{3}$ algorithm for this problem, Robertson and Seymour introduced the irrelevant vertex technique according to which in every instance of treewidth greater than $g(k)$ there is an "irrelevant" vertex whose removal creates an equivalent instance of the problem. This fact is based on the celebrated Unique Linkage Theorem, whose - very technical - proof gives a function $g(k)$ that is responsible for an immense parameter dependence in the running time of the algorithm. In this paper we give a new and self-contained proof of this result that strongly exploits the combinatorial properties of planar graphs and achieves $g(k)=O(k^{3/2}\cdot 2^{k}).$ Our bound is radically better than the bounds known for general graphs.

Linear kernels for edge deletion problems to immersion-closed graph classes

Suppose $\mathcal{F}$ is a finite family of graphs. We consider the following meta-problem, called $\mathcal{F}$ -Immersion Deletion: given a graph $G$ and integer $k$ , decide whether the deletion of at most $k$ edges of $G$ can result in a graph that does not contain any graph from $\mathcal{F}$ as an immersion. This problem is a close relative of the $\mathcal{F}$ -Minor Deletion problem studied by Fomin et al. [FOCS 2012], where one deletes vertices in order to remove all minor models of graphs from $\mathcal{F}$ . We prove that whenever all graphs from $\mathcal{F}$ are connected and at least one graph of $\mathcal{F}$ is planar and subcubic, then the $\mathcal{F}$ -Immersion Deletion problem admits: a constant-factor approximation algorithm running in time $O(m^3 \cdot n^3 \cdot \log m)$ ; a linear kernel that can be computed in time $O(m^4 \cdot n^3 \cdot \log m)$ ; and a $O(2^{O(k)} + m^4 \cdot n^3 \cdot \log m)$ -time fixed-parameter algorithm, where $n,m$ count the vertices and edges of the input graph. These results mirror the findings of Fomin et al. [FOCS 2012], who obtained a similar set of algorithmic results for $\mathcal{F}$ -Minor Deletion, under the assumption that at least one graph from $\mathcal{F}$ is planar. An important difference is that we are able to obtain a linear kernel for $\mathcal{F}$ -Immersion Deletion, while the exponent of the kernel of Fomin et al. for $\mathcal{F}$ -Minor Deletion depends heavily on the family $\mathcal{F}$ . In fact, this dependence is unavoidable under plausible complexity assumptions, as proven by Giannopoulou et al. [ICALP 2015]. This reveals that the kernelization complexity of $\mathcal{F}$ -Immersion Deletion is quite different than that of $\mathcal{F}$ -Minor Deletion.

Packing and Covering Immersion Models of Planar subcubic Graphs

A graph $H$ is an immersion of a graph $G$ if $H$ can be obtained by some sugraph $G$ after lifting incident edges. We prove that there is a polynomial function $f:\Bbb{N}\times\Bbb{N}\rightarrow\Bbb{N}$ , such that if $H$ is a connected planar subcubic graph on $h>0$ edges, $G$ is a graph, and $k$ is a non-negative integer, then either $G$ contains $k$ vertex/edge-disjoint subgraphs, each containing $H$ as an immersion, or $G$ contains a set $F$ of $f(k,h)$ vertices/edges such that $G\setminus F$ does not contain $H$ as an immersion.

Recent techniques and results on the Erdős-Pósa property

Several min-max relations in graph theory can be expressed in the framework of the Erdős-Pósa property. Typically, this property reveals a connection between packing and covering problems on graphs. We describe some recent techniques for proving this property that are related to tree-like decompositions. We also provide an unified presentation of the current state of the art on this topic.

The Parameterized Complexity of Graph Cyclability

The cyclability of a graph is the maximum integer $k$ for which every $k$ vertices lie on a cycle. The algorithmic version of the problem, given a graph $G$ and a non-negative integer $k,$ decide whether the cyclability of $G$ is at least $k,$ is {\sf NP}-hard. We study the parametrized complexity of this problem. We prove that this problem, parameterized by $k,$ is ${\sf co\mbox{-}W[1]}$-hard and that its does not admit a polynomial kernel on planar graphs, unless ${\sf NP}\subseteq{\sf co}\mbox{-}{\sf NP}/{\sf poly}$. On the positive side, we give an {\sf FPT} algorithm for planar graphs that runs in time $2^{2^{O(k^2\log k)}}\cdot n^2$ . Our algorithm is based on a series of graph-theoretical results on cyclic linkages in planar graphs.

The Structure of $W_4$ -Immersion-Free Graphs

We study the structure of graphs that do not contain the wheel on 5 vertices W4 as an immersion, and show that these graphs can be constructed via 1, 2, and 3-edge-sums from subcubic graphs and graphs of bounded treewidth.

An alternative proof for the constructive Asymmetric Lovász Local Lemma

We provide an alternative constructive proof of the Asymmetric Lovász Local Lemma. Our proof uses the classic algorithmic framework of Moser and the analysis introduced by Giotis, Kirousis, Psaromiligkos, and Thilikos in "On the algorithmic Lovász Local Lemma and acyclic edge coloring", combined with the work of Bender and Richmond on the multivariable Lagrange Inversion formula.

An edge variant of the Erdős-Pósa property

For every $r\in \mathbb{N}$ , we denote by $θ_{r}$ the multigraph with two vertices and $r$ parallel edges. Given a graph $G$ , we say that a subgraph $H$ of $G$ is a model of $θ_{r}$ in $G$ if $H$ contains $θ_{r}$ as a contraction. We prove that the following edge variant of the Erd{\H o}s-P{ó}sa property holds for every $r\geq 2$ : if $G$ is a graph and $k$ is a positive integer, then either $G$ contains a packing of $k$ mutually edge-disjoint models of $θ_{r}$ , or it contains a set $S$ of $f_r(k)$ edges such that $G\setminus S$ has no $θ_{r}$ -model, for both $f_r(k) = O(k^2r^3 \mathrm{polylog}~kr)$ and $f_r(k) = O(k^4r^2 \mathrm{polylog}~kr).$

Contraction Obstructions for Connected Graph Searching

We consider the connected variant of the classic mixed search game where, in each search step, cleaned edges form a connected subgraph. We consider graph classes with bounded connected (and monotone) mixed search number and we deal with the question whether the obstruction set, with respect of the contraction partial ordering, for those classes is finite. In general, there is no guarantee that those sets are finite, as graphs are not well quasi ordered under the contraction partial ordering relation. In this paper we provide the obstruction set for $k=2$ , where $k$ is the number of searchers we are allowed to use. This set is finite, it consists of 177 graphs and completely characterises the graphs with connected (and monotone) mixed search number at most 2. Our proof reveals that the "sense of direction" of an optimal search searching is important for connected search which is in contrast to the unconnected original case. We also give a double exponential lower bound on the size of the obstruction set for the classes where this set is finite.

Editing to a Planar Graph of Given Degrees

We consider the following graph modification problem. Let the input consist of a graph $G=(V,E)$ , a weight function $w\colon V\cup E\rightarrow \mathbb{N}$ , a cost function $c\colon V\cup E\rightarrow \mathbb{N}$ and a degree function $δ\colon V\rightarrow \mathbb{N}_0$ , together with three integers $k_v, k_e$ and $C$ . The question is whether we can delete a set of vertices of total weight at most $k_v$ and a set of edges of total weight at most $k_e$ so that the total cost of the deleted elements is at most $C$ and every non-deleted vertex $v$ has degree $δ(v)$ in the resulting graph $G'$ . We also consider the variant in which $G'$ must be connected. Both problems are known to be NP-complete and W[1]-hard when parameterized by $k_v+k_e$ . We prove that, when restricted to planar graphs, they stay NP-complete but have polynomial kernels when parameterized by $k_v+k_e$ .

Low Polynomial Exclusion of Planar Graph Patterns

The celebrated grid exclusion theorem states that for every $h$ -vertex planar graph $H$ , there is a constant $c_{h}$ such that if a graph $G$ does not contain $H$ as a minor then $G$ has treewidth at most $c_{h}$ . We are looking for patterns of $H$ where this bound can become a low degree polynomial. We provide such bounds for the following parameterized graphs: the wheel ( $c_{h}=O(h)$ ), the double wheel ( $c_{h}=O(h^2\cdot \log^{2} h)$ ), any graph of pathwidth at most 2 ( $c_{h}=O(h^{2})$ ), and the yurt graph ( $c_{h}=O(h^{4})$ ).

Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism

In this paper we design {\sf FPT}-algorithms for two parameterized problems. The first is \textsc{List Digraph Homomorphism}: given two digraphs $G$ and $H$ and a list of allowed vertices of $H$ for every vertex of $G$ , the question is whether there exists a homomorphism from $G$ to $H$ respecting the list constraints. The second problem is a variant of \textsc{Multiway Cut}, namely \textsc{Min-Max Multiway Cut}: given a graph $G$ , a non-negative integer $\ell$ , and a set $T$ of $r$ terminals, the question is whether we can partition the vertices of $G$ into $r$ parts such that (a) each part contains one terminal and (b) there are at most $\ell$ edges with only one endpoint in this part. We parameterize \textsc{List Digraph Homomorphism} by the number $w$ of edges of $G$ that are mapped to non-loop edges of $H$ and we give a time $2^{O(\ell\cdot\log h+\ell^2\cdot \log \ell)}\cdot n^{4}\cdot \log n$ algorithm, where $h$ is the order of the host graph $H$ . We also prove that \textsc{Min-Max Multiway Cut} can be solved in time $2^{O((\ell r)^2\log \ell r)}\cdot n^{4}\cdot \log n$ . Our approach introduces a general problem, called {\sc List Allocation}, whose expressive power permits the design of parameterized reductions of both aforementioned problems to it. Then our results are based on an {\sf FPT}-algorithm for the {\sc List Allocation} problem that is designed using a suitable adaptation of the {\em randomized contractions} technique (introduced by [Chitnis, Cygan, Hajiaghayi, Pilipczuk, and Pilipczuk, FOCS 2012]).

Planar Disjoint-Paths Completion

introduce {\sc Planar Disjoint Paths Completion}, a completion counterpart of the Disjoint Paths problem, and study its parameterized complexity. The problem can be stated as follows: given a, not necessarily connected, plane graph $G,$ $k$ pairs of terminals, and a face $F$ of $G,$ find a minimum-size set of edges, if one exists, to be added inside $F$ so that the embedding remains planar and the pairs become connected by $k$ disjoint paths in the augmented network. Our results are twofold: first, we give an upper bound on the number of necessary additional edges when a solution exists. This bound is a function of $k$ , independent of the size of $G.$ Second, we show that the problem is fixed-parameter tractable, in particular, it can be solved in time $f(k)\cdot n^{2}.$

Variants of Plane Diameter Completion

The {\sc Plane Diameter Completion} problem asks, given a plane graph $G$ and a positive integer $d$ , if it is a spanning subgraph of a plane graph $H$ that has diameter at most $d$ . We examine two variants of this problem where the input comes with another parameter $k$ . In the first variant, called BPDC, $k$ upper bounds the total number of edges to be added and in the second, called BFPDC, $k$ upper bounds the number of additional edges per face. We prove that both problems are {\sf NP}-complete, the first even for 3-connected graphs of face-degree at most 4 and the second even when $k=1$ on 3-connected graphs of face-degree at most 5. In this paper we give parameterized algorithms for both problems that run in $O(n^{3})+2^{2^{O((kd)^2\log d)}}\cdot n$ steps.

preprint2014arXiv

A Polynomial-time Algorithm for Outerplanar Diameter Improvement

The Outerplanar Diameter Improvement problem asks, given a graph $G$ and an integer $D$ , whether it is possible to add edges to $G$ in a way that the resulting graph is outerplanar and has diameter at most $D$ . We provide a dynamic programming algorithm that solves this problem in polynomial time. Outerplanar Diameter Improvement demonstrates several structural analogues to the celebrated and challenging Planar Diameter Improvement problem, where the resulting graph should, instead, be planar. The complexity status of this latter problem is open.

preprint2014arXiv

Explicit linear kernels via dynamic programming

Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result of Bodlaender et al. [FOCS 2009] on graphs of bounded genus, then generalized by Fomin et al. [SODA 2010] to graphs excluding a fixed minor, and by Kim et al. [ICALP 2013] to graphs excluding a fixed topological minor. Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions but, mainly due to their generality, it is not clear how to derive from them constructive kernels with explicit constants. In this paper we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that, instead of expressibility in CMSO logic, uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for $r$ -Dominating Set and $r$ -Scattered Set on apex-minor-free graphs, and for Planar-\mathcal{F}-Deletion on graphs excluding a fixed (topological) minor in the case where all the graphs in \mathcal{F} are connected.

(Meta) Kernelization

In a parameterized problem, every instance I comes with a positive integer k. The problem is said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the instance I to a polynomial in k, while preserving the answer. In this work we give two meta-theorems on kernelzation. The first theorem says that all problems expressible in Counting Monadic Second Order Logic and satisfying a coverability property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker coverability property admit a linear kernel on graphs of bounded genus. These theorems unify and extend all previously known kernelization results for planar graph problems.

Bidimensionality of Geometric Intersection Graphs

Let B be a finite collection of geometric (not necessarily convex) bodies in the plane. Clearly, this class of geometric objects naturally generalizes the class of disks, lines, ellipsoids, and even convex polygons. We consider geometric intersection graphs GB where each body of the collection B is represented by a vertex, and two vertices of GB are adjacent if the intersection of the corresponding bodies is non-empty. For such graph classes and under natural restrictions on their maximum degree or subgraph exclusion, we prove that the relation between their treewidth and the maximum size of a grid minor is linear. These combinatorial results vastly extend the applicability of all the meta-algorithmic results of the bidimensionality theory to geometrically defined graph classes.

Excluding Graphs as Immersions in Surface Embedded Graphs

We prove a structural characterization of graphs that forbid a fixed graph $H$ as an immersion and can be embedded in a surface of Euler genus $γ$ . In particular, we prove that a graph $G$ that excludes some connected graph $H$ as an immersion and is embedded in a surface of Euler genus $γ$ has either "small" treewidth (bounded by a function of $H$ and $γ$ ) or "small" edge connectivity (bounded by the maximum degree of $H$ ). Using the same techniques we also prove an excluded grid theorem on bounded genus graphs for the immersion relation.

Nearly Planar Graphs and λ-flat Graphs

A graph G is ξ-nearly planar if it can be embedded in the sphere so that each of its edges is crossed at most ξ times. The family of ξ-nearly planar graphs is widely extending the notion of planarity. We introduce an alternative parameterized graph family extending the notion of planarity, the λ-flat graphs, this time defined as powers of plane graphs in regard to a novel notion of distance, the wall-by-wall distance. We show that the two parameterized graph classes are parametrically equivalent.

Polynomial Gap Extensions of the Erdős-Pósa Theorem

Given a graph $H$ , we denote by ${\cal M}(H)$ all graphs that can be contracted to $H$ . The following extension of the Erdős-Pósa Theorem holds: for every $h$ -vertex planar graph $H$ , there exists a function $f_{H}$ such that every graph $G$ , either contains $k$ disjoint copies of graphs in ${\cal M}(H)$ , or contains a set of $f_{H}(k)$ vertices meeting every subgraph of $G$ that belongs in ${\cal M}(H)$ . In this paper we prove that this is the case for every graph $H$ of pathwidth at most 2 and, in particular, that $f_{H}(k) = 2^{O(h^2)}\cdot k^{2}\cdot \log k$ . As a main ingredient of the proof of our result, we show that for every graph $H$ on $h$ vertices and pathwidth at most 2, either $G$ contains $k$ disjoint copies of $H$ as a minor or the treewidth of $G$ is upper-bounded by $2^{O(h^2)}\cdot k^{2}\cdot \log k$ . We finally prove that the exponential dependence on $h$ in these bounds can be avoided if $H=K_{2,r}$ . In particular, we show that $f_{K_{2,r}}=O(r^2\cdot k^2)$

preprint2012arXiv

Forbidding Kuratowski Graphs as Immersions

The immersion relation is a partial ordering relation on graphs that is weaker than the topological minor relation in the sense that if a graph $G$ contains a graph $H$ as a topological minor, then it also contains it as an immersion but not vice versa. Kuratowski graphs, namely $K_{5}$ and $K_{3,3}$ , give a precise characterization of planar graphs when excluded as topological minors. In this note we give a structural characterization of the graphs that exclude Kuratowski graphs as immersions. We prove that they can be constructed by applying consecutive $i$ -edge-sums, for $i\leq 3$ , starting from graphs that are planar sub-cubic or of branch-width at most 10.

Asymptotic Enumeration of Non-crossing Partitions on Surfaces

We generalize the notion of non-crossing partition on a disk to general surfaces with boundary. For this, we consider a surface $Σ$ and introduce the number $C_Σ(n)$ of non-crossing partitions of a set of $n$ points laying on the boundary of $Σ$ . Our proofs use bijective techniques arising from map enumeration, joint with the symbolic method and singularity analysis on generating functions. An outcome of our results is that the exponential growth of $C_Σ(n)$ is the same as the one of the $n$ -th Catalan number, i.e., does not change when we move from the case where $Σ$ is a disk to general surfaces with boundary.

Confronting Intractability via Parameters

One approach to confronting computational hardness is to try to understand the contribution of various parameters to the running time of algorithms and the complexity of computational tasks. Almost no computational tasks in real life are specified by their size alone. It is not hard to imagine that some parameters contribute more intractability than others and it seems reasonable to develop a theory of computational complexity which seeks to exploit this fact. Such a theory should be able to address the needs of practicioners in algorithmics. The last twenty years have seen the development of such a theory. This theory has a large number of successes in terms of a rich collection of algorithmic techniques both practical and theoretical, and a fine-grained intractability theory. Whilst the theory has been widely used in a number of areas of applications including computational biology, linguistics, VLSI design, learning theory and many others, knowledge of the area is highly varied. We hope that this article will show both the basic theory and point at the wide array of techniques available. Naturally the treatment is condensed, and the reader who wants more should go to the texts, Downey and Fellows, Flum and Grohe, Niedermeier, and the upcoming undergraduate text Downey and Fellows.

Dynamic Programming for Graphs on Surfaces

We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic programming runs in 2^{O(k log k)} n steps. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called "surface cut decomposition", generalizing sphere cut decompositions of planar graphs introduced by Seymour and Thomas, which has nice combinatorial properties. Namely, the number of partial solutions that can be arranged on a surface cut decomposition can be upper-bounded by the number of non-crossing partitions on surfaces with boundary. It follows that partial solutions can be represented by a single-exponential (in the branchwidth k) number of configurations. This proves that, when applied on surface cut decompositions, dynamic programming runs in 2^{O(k)} n steps. That way, we considerably extend the class of problems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improve most previous results in this direction.