We investigate the problem of strong connectivity augmentation within plane oriented graphs. We show that deciding whether a plane oriented graph D can be augmented with (any number of) arcs X such that D+X is strongly connected, but still plane and oriented, is NP-hard. The hardness also holds for the planar variant. This question becomes trivial within plane (or planar) digraphs, like most connectivity augmentation problems without a budget constraint. The budgeted variant, Plane Strong Connectivity Augmentation (PSCA) considers a plane oriented graph D along with some integer k, and asks for an X of size at most k ensuring that D+X is strongly connected, while remaining plane and oriented. Our main result is a fixed-parameter tractable algorithm for PSCA, running in time 2^O(k) n² log n. The cornerstone of our procedure is a structural result showing that, for any fixed k, each face admits a bounded number of partial solutions "dominating" all others. Then, our algorithm for PSCA combines face-wise branching with a randomized reduction to the polynomial Minimum Dijoin problem, yielding a Monte-Carlo FPT algorithm, which we derandomize. To the best of our knowledge, this is the first FPT algorithm for a (hard) connectivity augmentation problem constrained by planarity.

We introduce the notion of colorful minors, which generalizes the classical concept of rooted minors in graphs. A $q$-colorful graph= is defined as a pair $(G, χ),$ where $G$ is a graph and $χ$ assigns to each vertex a (possibly empty) subset of at most $q$ colors. The colorful minor relation enhances the classical minor relation by merging color sets at contracted edges and allowing the removal of colors from vertices. This framework naturally models algorithmic problems involving graphs with (possibly overlapping) annotated vertex sets. We develop a structural theory for colorful minors by establishing three core theorems characterizing $\mathcal{H}$-colorful minor-free graphs, where $\mathcal{H}$ consists either of a clique or a grid with all vertices assigned all colors, or of grids with colors segregated and ordered on the outer face. Our results reveal that when exclusion is imposed not only on graphs but also to the way colors are distributed in them, a more refined structural landscape appears. On the algorithmic side, we deduce that colorful minor testing is fixed-parameter tractable. Together with the fact that the colorful minor relation forms a well-quasi-order, this implies that every colorful minor-monotone parameter on colorful graphs admits a fixed-parameter algorithm. Furthermore, we derive two algorithmic meta-theorems (AMTs) whose structural conditions are linked to extensions of treewidth and Hadwiger number on colorful graphs. Our results suggest how known AMTs can be extended to incorporate not only the structure of the input graph but also the way the colored vertices are distributed in it.

Algorithmic meta-theorems explain the tractability of large classes of computational problems by linking logical expressibility with structural graph properties. While extensions of first-order logic such as FO+dp admit efficient model checking on graph classes excluding a fixed topological minor, comparable results for richer fragments of CMSO were previously unknown. We further develop the framework of Sau, Stamoulis, and Thilikos [SODA 2025] for fragmenting CMSO via annotated graph parameters, which restrict set quantification to vertex sets satisfying bounded structural conditions. Following this approach, we identify a fragment of CMSO, namely the one defined by allowing quantification only over sets having what we call low monodimensionality, that generalizes several previously-known logics and we show that model checking for this fragment, enhanced with the disjoint-paths predicate, is fixed-parameter tractable on topological-minor-free graph classes. Such classes essentially delimit the tractability for this logic on subgraph-closed classes. As a consequence, our results lift several known algorithmic meta-theorems beyond first-order logic to the topological-minor-free setting.

We introduce a series of graph decompositions based on the modulator/target scheme of modification problems that enable several algorithmic applications that parametrically extend the algorithmic potential of planarity. In the core of our approach is a polynomial time algorithm for computing planar \(\mathcal{H}\)-modulators. Given a graph class \(\mathcal{H}\), a planar \(\mathcal{H}\)-modulator of a graph \(G\) is a set \(X \subseteq V(G)\) such that the “torso” of \(X\) is planar and all connected components of \(G-X\) belong to \(\mathcal{H}\). Here, the torso of \(X\) is obtained from \(G[X]\) if, for every connected component of \(G-X\), we form a clique out of its neighborhood on \(G[X]\). We introduce \(\mathcal{H}\)-Planarity as the problem of deciding whether a graph \(G\) has a planar \(\mathcal{H}\)-modulator. We prove that, if \(\mathcal{H}\) is hereditary, CMS0-definable, and decidable in polynomial time, then \(\mathcal{H}\)-Planarity is solvable in polynomial time.

We show that every \(H\)-minor-free graph that also excludes a \((k \times k)\)-grid as a minor has treewidth/branchwidth bounded from above by a function \(f(t,k)\) that is linear in \(k\) and polynomial in \(t := |V(H)|\). Such a result was proven originally by [Demaine & Hajiaghayi, Combinatorica, 2008], where \(f\) was indeed linear in \(k\). However the dependency in \(t\) in this result was non-explicit (and huge). Later, [Kawarabayashi & Kobayashi, JCTB, 2020] showed that this bound can be estimated to be \(f(t,k) \in 2^{\mathcal O(t \log t)} \cdot k\). Wood recently asked whether \(f\) can be pushed further to be polynomial, while maintaining the linearity on \(k\). We answer this in a particularly strong sense, by showing that the treewidth/branchwidth of \(G\) is in \(\mathcal O(gk + t^{2304})\), where \(g\) is the Euler genus of \(H\). This directly yields \(f(t,k) = \mathcal O(t^2 k + t^{2304})\).

Given a graph class 𝒢, the limiting density of 𝒢 is defined as δ(𝒢) = lim_{n → ∞} ex(𝒢,n)/n where ex(𝒢,n) is the maximum number of edges of a graph in 𝒢 on n vertices. The limiting density δ(𝒢) is known to be a rational number when 𝒢 is a minor-closed graph class. For every δ ∈ [0,3/2), we prove that the set of ⊆-minimal minor-closed graph classes with densities > δ is finite and we identify it completely. A consequence of our results is an algorithm that, given a finite set of graphs 𝒵, of total size n, either outputs the value of δ(excl(𝒵)) or reports that δ(excl(𝒵)) ≥ 3/2, where excl(𝒵) is the class of graphs excluding the graphs in 𝒵 as minors. The algorithm runs in 2^{poly(n)} time.

Temporal graphs are graphs that evolve over time. Many problems which are polynomial-time solvable in standard graphs become NP -hard when appropriately defined in the realm of temporal graphs. This suggested the definition of several parameters for temporal graphs and to prove the fixed-parameter tractability of several problems with respect to these parameters. In this paper, we introduce a hierarchy of parameters based on the previously defined interval membership width and on the temporal evolution of the connected components of the underlying static graph. We then show that the Eulerian trail problem and the temporal 2-coloring problem are both fixed-parameter tractable (in short, FPT ) with respect to any of the parameters in the hierarchy. We also introduce a vertex-variant of the parameters and we show that the firefighter problem (which was known to be FPT with respect to the vertex-variant of the interval membership width) is also FPT with respect to one of the parameters in the second level of the hierarchy.

A replacement action is a function ℒ that maps each graph H to a collection of graphs of size at most |V(H)|. Given a graph class ℋ, we consider a general family of graph modification problems, called ℒ-Replacement to ℋ, where the input is a graph G and the question is whether it is possible to replace some induced subgraph H₁ of G on at most k vertices by a graph H₂ in ℒ(H₁) so that the resulting graph belongs to ℋ. ℒ-Replacement to ℋ can simulate many graph modification problems including vertex deletion, edge deletion/addition/edition/contraction, vertex identification, subgraph complementation, independent set deletion, (induced) matching deletion/contraction, etc. We present two algorithms. The first one solves ℒ-Replacement to ℋ in time 2^poly(k) ⋅ |V(G)|² for every minor-closed graph class ℋ, where poly is a polynomial whose degree depends on ℋ, under a mild technical condition on ℒ. This generalizes the results of Morelle, Sau, Stamoulis, and Thilikos [ICALP 2020, ICALP 2023] for the particular case of Vertex Deletion to ℋ within the same running time. Our second algorithm is an improvement of the first one when ℋ is the class of graphs embeddable in a surface of Euler genus at most g and runs in time 2^𝒪(k⁹) ⋅ |V(G)|², where the 𝒪(⋅) notation depends on g. To the best of our knowledge, these are the first parameterized algorithms with a reasonable parametric dependence for such a general family of graph modification problems to minor-closed classes.

The irrelevant vertex technique provides a powerful tool for the design of parameterized algorithms for a wide variety of problems on graphs. A common characteristic of these problems, permitting the application of this technique on surface-embedded graphs, is the fact that every graph of large enough treewidth contains a vertex that is irrelevant, in the sense that its removal yields an equivalent instance of the problem. The straightforward application of this technique yields algorithms with running time that is quadratic in the size of the input graph. This running time is due to the fact that it takes linear time to detect one irrelevant vertex and the total number of irrelevant vertices to be detected is linear as well. Using advanced techniques, sub-quadratic algorithms have been designed for particular problems, even in general graphs. However, designing a general framework for linear-time algorithms has been open, even for the bounded-genus case. In this paper we introduce a general framework that enables finding in linear time an entire set of irrelevant vertices whose removal yields a bounded-treewidth graph, provided that the input graph has bounded genus. Our technique consists in decomposing any surface-embedded graph into a tree-structured collection of bounded-treewidth subgraphs where detecting globally irrelevant vertices can be done locally and independently. Our method is applicable to a wide variety of known graph containment or graph modification problems where the irrelevant vertex technique applies. Examples include the (Induced) Minor Folio problem, the (Induced) Disjoint Paths problem, and the F-Minor-Deletion problem.

Given a graph G and a vertex set X, the annotated treewidth tw(G,X ) of X in G is the maximum treewidth of an X-rooted minor of G, i.e., a minor H where the model of each vertex of H contains some vertex of X. That way, tw(G, X ) can be seen as a measure of the contribution of X to the tree-decomposability of G. We introduce the logic CMSO/tw as the fragment of monadic second-order logic on graphs obtained by restricting set quantification to sets of bounded annotated treewidth. We prove the following Algorithmic Meta-Theorem (AMT): for every non-trivial minor-closed graph class, model checking for CMSO/tw formulas can be done in quadratic time. Our proof works for the more general CMSO/tw+dp logic, that is CMSO/tw enhanced by disjoint-path predicates. Our AMT can be seen as an extension of Courcelle’s theorem to minor-closed graph classes where the bounded-treewidth condition in the input graph is replaced by the bounded-treewidth quantification in the formulas. Our results yield, as special cases, all known AMTs whose combinatorial restriction is non-trivial minor-closedness.

The Weighted F - Vertex Deletion for a class F of graphs asks, weighted graph G , for a minimum weight vertex set S such that G − S ∈ F . The case when F is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted F - Vertex Deletion . Only three cases of minor-closed F are known to admit constant-factor approximations, namely Vertex Cover , Feedback Vertex Set and Diamond Hitting Set . We study the problem for the class F of θ c -minor-free graphs, under the equivalent setting of the Weighted c -Bond Cover problem, and present a constant-factor approximation algorithm using the primal-dual method. Besides making an important step in the quest of (dis)proving a constant-factor approximation for Weighted F - Vertex Deletion , our result may be useful as a template for algorithms for other minor-closed families.

We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence , defining some property of the modified part of the graph, and the target sentence , defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic ( CMSO ) and have models of bounded treewidth, while target sentences express first-order logic ( FO ) properties. Our logic captures problems that are not definable in FO and, moreover, may have instances of unbounded treewidth. Our main result is that, for this compound logic, model-checking can be done in quadratic time on minor-free graphs. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique . It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle’s theorem does not apply. The proof of our meta-theorem combines novel combinatorial results related to the Flat Wall theorem along with elements of the proof of Courcelle’s theorem and Gaifman’s theorem. Our algorithmic meta-theorem encompasses, unifies, and extends the known meta-algorithmic results for CMSO and FO on minor-closed graph classes.

Let$\mathcal{G}$and$\mathcal{H}$be minor-closed graph classes. We say that the pair$(\mathcal{H},\ \mathcal{G})$is an Erdös-Pósa pair (EP-pair) if there exists a function$f$such that for every$k$and every graph$G\in \mathcal{G}$, either$G$has$k$pairwise vertex-disjoint sub graphs which do not belong to$\mathcal{H}$, or there exists a set$S\subseteq V(G)$of size at most$f(k)$for which$G-S\in \mathcal{H}$. The classic result of Erdös and Pósa says that if$\mathcal{F}$is the class of forests, then$(\mathcal{F}, \mathcal{G})$is an EP-pair for all graph classes$\mathcal{G}$. A minor-closed graph class$\mathcal{G}$is an EP-counterexample for$\mathcal{H}$if$\mathcal{G}$is minimal with the property that$(\mathcal{H},\ \mathcal{G})$is not an EP-pair. In this paper, we prove that for every minor-closed graph class$\mathcal{H}$the set$\mathfrak{C}_{\mathcal{H}}$of all EP-counterexamples for$\mathcal{H}$is finite. In particular, we provide a complete characterization of$\mathfrak{C}_{\mathcal{H}}$for every$\mathcal{H}$and give a constructive upper bound on its size. We show that each class$\mathcal{G}$in$\mathfrak{C}_{\mathcal{H}}$can be described as the set of all minors of some, suitably defined, sequence of grid-like graphs$\langle{W}_{k}\rangle_{k\in \mathbb{N}}$. Moreover, each$\mathrm{W}_{k}$admits a half-integral packing, i.e.,$k$copies of some$H\not\in \mathcal{H}$where no vertex is used more than twice. This implies a complete delineation of the half-integrality threshold of the Erdös-Pósa property for minors and as a corollary, we obtain a constructive proof of Thomas' conjecture on the half-integral Erdös-Pósa property for minors which was recently confirmed by Liu. Our results are algorithmic. Let$h=h(\mathcal{H})$denote the maximum size of an obstruction to$\mathcal{H}$. For every minor-closed graph class$\mathcal{H}$, we construct an algorithm that, given a graph$G$and an integer$k$, either outputs a half-integral packing of$k$copies of some$H\not\in \mathcal{H}$or outputs a set of at most$2^{k^{\overline{\mathcal{O}}_{h}(1)}}$vertices whose deletion creates a graph in$\mathcal{H}$in time$2^{2^{k^{\mathcal{O}_{h}(1)}}}\cdot\vert G\vert ^{4}\log\vert G\vert$. Moreover, as a consequence of our results, for every minor-closed class$\mathcal{H}$, we obtain min-max-dualities, which may be seen as analogues of the celebrated Grid Theorem of Robertson and Seymour, for the recently introduced parameters$\mathcal{H}$-treewidth and elimination distance to$\mathcal{H}$.

In 1986 Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa property for minors if and only if it is planar. In particular, for every non-planar graph H they gave examples showing that the Erdős-Pósa property does not hold for H. Recently, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erdős-Pósa property for minors. Liu’s proof is non-constructive and to this date, with the exception of a small number of examples, no constructive proof is known. In this paper, we initiate the delineation of the half-integrality of the Erdős-Pósa property for minors. We conjecture that for every graph H, there exists a unique (up to a suitable equivalence relation on graph parameters) graph parameter EP_H such that H has the Erdős-Pósa property in a minor-closed graph class 𝒢 if and only if sup{EP_H(G) ∣ G ∈ 𝒢} is finite. We prove this conjecture for the class ℋ of Kuratowski-connected shallow-vortex minors by showing that, for every non-planar H ∈ ℋ, the parameter EP_H(G) is precisely the maximum order of a Robertson-Seymour counterexample to the Erdős-Pósa property of H which can be found as a minor in G. Our results are constructive and imply, for the first time, parameterized algorithms that find either a packing, or a cover, or one of the Robertson-Seymour counterexamples, certifying the existence of a half-integral packing for the graphs in ℋ.

Disjoint-paths logic, denoted FO+ DP, extends first-order logic (FO) with atomic predicates dpk[(x1, y1), …, (xk, yk)], expressing the existence of internally vertex-disjoint paths between xi and yi, for 1 ≤ i ≤ k. We prove that for every graph class excluding some fixed graph as a topological minor, the model checking problem for FO+ DP is fixed-parameter tractable. This extends the model checking algorithm of Golovach et al. [SODA 2023] for FO+ DP for minor-closed graph classes. It also essentially settles the question of tractable model checking for this logic on subgraph-closed classes, since the problem is hard on subgraph-closed classes not excluding a topological minor (assuming a further mild condition on efficiency of encoding).

The Graph Minors Structure Theorem of Robertson and Seymour asserts that, for every graph H , every H -minor-free graph can be obtained by clique-sums of “almost embeddable” graphs. Here a graph is “almost embeddable” if it can be obtained from a graph of bounded Euler-genus by pasting graphs of bounded pathwidth in an “orderly fashion” into a bounded number of faces, called the vortices , and then adding a bounded number of additional vertices, called apices , with arbitrary neighborhoods. Our main result is a full classification of all graphs H for which the use of vortices in the theorem above can be avoided. To this end, we identify a (parametric) graph \(\mathscr{S}_{t}\) and prove that all \(\mathscr{S}_{t}\) -minor-free graphs can be obtained by clique-sums of graphs embeddable in a surface of bounded Euler-genus after deleting a bounded number of vertices. We show that this result is tight in the sense that the appearance of vortices cannot be avoided for H -minor-free graphs, whenever H is not a minor of \(\mathscr{S}_{t}\) for some \(t\in \mathbb {N}\) . Using our new structure theorem, we design an algorithm that, given an \(\mathscr{S}_{t}\) -minor-free graph G , computes the generating function of all perfect matchings of G in polynomial time. Our results, combined with known complexity results, imply a complete characterization of minor-closed graph classes where the number of perfect matchings is polynomially computable: They are exactly those graph classes that do not contain every \(\mathscr{S}_{t}\) as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes.

We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence, defining some property of the modified part of the graph, and the target sentence, defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic (CMSOL) and have models of bounded treewidth, while target sentences express first-order logic (FOL) properties along with minor-exclusion. Our logic captures problems that are not definable in first-order logic and, moreover, may have instances of unbounded treewidth. Also, it permits the modeling of wide families of problems involving vertex/edge removals, alternative modulator measures (such as elimination distance or $\mathcal{G}$-treewidth), multistage modifications, and various cut problems. Our main result is that, for this compound logic, model-checking can be done in quadratic time. All derived algorithms are constructive and this, as a byproduct, extends the constructibility horizon of the algorithmic applications of the Graph Minors theorem of Robertson and Seymour. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique. It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle's theorem does not apply. The proof of our meta-theorem combines novel combinatorial results related to the Flat Wall theorem along with elements of the proof of Courcelle's theorem and Gaifman's theorem. We finally prove extensions where the target property is expressible in FOL+DP, i.e., the enhancement of FOL with disjoint-paths predicates.

Let G be a minor-closed graph class and let G be an n-vertex graph. We say that G is a k-apex of G if G contains a set S of at most k vertices such that G⧵S belongs to G. Our first result is an algorithm that decides whether G is a k-apex of G in time 2^poly(k)⋅n². This algorithm improves the previous one, given by Sau, Stamoulis, and Thilikos [ICALP 2020, TALG 2022], whose running time was 2^poly(k)⋅n³. The elimination distance of G to G, denoted by ed_G(G), is the minimum number of rounds required to reduce each connected component of G to a graph in G by removing one vertex from each connected component in each round. Bulian and Dawar [Algorithmica 2017] proved the existence of an FPT-algorithm, with parameter k, to decide whether ed_G(G) ≤ k. This algorithm is based on the computability of the minor-obstructions and its dependence on k is not explicit. We extend the techniques used in the first algorithm to decide whether ed_G(G) ≤ k in time 2^{2^{2^poly(k)}}⋅n². This is the first algorithm for this problem with an explicit parametric dependence in k. In the special case where G excludes some apex-graph as a minor, we give two alternative algorithms, one running in time 2^{2^O(k²log k)}⋅n² and one running in time 2^{poly(k)}⋅n³. As a stepping stone for these algorithms, we provide an algorithm that decides whether ed_G(G) ≤ k in time 2^O(tw⋅ k + tw log tw)⋅n, where tw is the treewidth of G. This algorithm combines the dynamic programming framework of Reidl, Rossmanith, Villaamil, and Sikdar [ICALP 2014] for the particular case where G contains only the empty graph (i.e., for treedepth) with the representative-based techniques introduced by Baste, Sau, and Thilikos [SODA 2020]. In all the algorithmic complexities above, poly is a polynomial function whose degree depends on G, while the hidden constants also depend on G. Finally, we provide explicit upper bounds on the size of the graphs in the minor-obstruction set of the class of graphs E_k(G) = {G ∣ ed_G(G) ≤ k}.

We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call bipartite tree decomposition. Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal number. Intuitively, a bipartite tree decomposition is a tree decomposition whose bags induce almost bipartite graphs and whose adhesions contain at most one vertex from the bipartite part of any other bag, while the width of such decomposition measures how far the bags are from being bipartite. Adapted from a tree decomposition originally defined by Demaine, Hajiaghayi, and Kawarabayashi [SODA 2010] and explicitly defined by Tazari [Theor. Comput. Sci. 2012], bipartite treewidth appears to play a crucial role for solving problems related to odd-minors, which have recently attracted considerable attention. As a first step toward a theory for solving these problems efficiently, the main goal of this paper is to develop dynamic programming techniques to solve problems on graphs of small bipartite treewidth. For such graphs, we provide a number of para-NP-completeness results, FPT-algorithms, and XP-algorithms, as well as several open problems. In particular, we show that K_t-Subgraph-Cover, Weighted Vertex Cover/Independent Set, Odd Cycle Transversal, and Maximum Weighted Cut are FPT parameterized by bipartite treewidth. We also provide the following complexity dichotomy when H is a 2-connected graph, for each of the H-Subgraph-Packing, H-Induced-Packing, H-Scattered-Packing, and H-Odd-Minor-Packing problems: if H is bipartite, then the problem is para-NP-complete parameterized by bipartite treewidth while, if H is non-bipartite, then the problem is solvable in XP-time. Beyond bipartite treewidth, we define 1-ℋ-treewidth by replacing the bipartite graph class by any graph class ℋ. Most of the technology developed here also works for this more general parameter.

We introduce a new kernelization tool, called rainbow matching technique, that is appropriate for the design of polynomial kernels for packing problems. Our technique capitalizes on the powerful combinatorial results of [Graf, Harris, Haxell, SODA 2021]. We apply the rainbow matching technique on two (di)graph packing problems, namely the TRIANGLE-PACKING IN TOURNAMENT problem (TPT), where we ask for a packing of k directed triangles in a tournament, and the INDUCED 2-PATH-PACKING (I2PP) where we ask for a packing of k induced paths of length two in a graph. The existence of a sub-quadratic kernels for these problems was proven for the first time in [Fomin, Le, Lokshtanov, Saurabh, Thomassé, Zehavi. ACM Trans. Algorithms, 2019], where they gave a kernel of

By a seminal result of Valiant, computing the permanent of (0,1)-matrices is, in general, #P-hard. In 1913 Polya asked for which (0,1)-matrices A it is possible to change some signs such that the permanent of A equals the determinant of the resulting matrix. In 1975, Little showed these matrices to be exactly the biadjacency matrices of bipartite graphs excluding K3,3 as a matching minor. This was turned into a polynomial time algorithm by McCuaig, Robertson, Seymour, and Thomas in 1999. However, the relation between the exclusion of some matching minor in a bipartite graph and the tractability of the permanent extends beyond K3,3. Recently it was shown that the exclusion of any planar bipartite graph as a matching minor yields a class of bipartite graphs on which the permanent of the corresponding (0,1)-matrices can be computed efficiently. In this paper we unify the two results above into a single, more general result in the style of the celebrated structure theorem for single-crossing-minor-free graphs. We identify a class of bipartite graphs strictly generalising planar bipartite graphs and K3,3 which includes infinitely many non-Pfaffian graphs. The exclusion of any member of this class as a matching minor yields a structure that allows for the efficient evaluation of the permanent. Moreover, we show that the evaluation of the permanent remains #P-hard on bipartite graphs which exclude K5,5 as a matching minor. This establishes a first computational lower bound for the problem of counting perfect matchings on matching minor closed classes. As another application of our structure theorem, we obtain a strict generalisation of the algorithm for the k-vertex disjoint directed paths problem on digraphs of bounded directed treewidth.

The disjoint paths logic, FOL+DP, is an extension of First-Order Logic (FOL) with the extra atomic predicate dpk(x1,y1,…, xk,yk), expressing the existence of internally vertex-disjoint paths between Xi and yi, for i ∈ {1,…, k}. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every proper minor-closed graph class, model-checking for FOL+DP can be done in quadratic time. We also introduce an extension of FOL+DP, namely the scattered disjoint paths logic, FOL+SDP, where we further consider the atomic predicate s-sdpk(x1,y1,…,xk,yk), demanding that the disjoint paths are within distance bigger than some fixed value s. Using the same technique we prove that model-checking for FOL+SDP can be done in quadratic time on classes of graphs with bounded Euler genus. * The full version of the paper can be accessed at https://arxiv.org/abs/2211.01723

We introduce the rendezvous game with adversaries. In this game, two players, Facilitator and Divider, play against each other on a graph. Facilitator has two agents and Divider has a team of k agents located in some vertices. They take turns in moving their agents to adjacent vertices (or staying put). Facilitator wins if his agents meet in some vertex. Divider aims to prevent the rendezvous of Facilitator's agents. We show that deciding whether Facilitator can win is PSPACE-hard and, when parameterized by k, co-W[2]-hard. Moreover, even deciding whether Facilitator can win within τ steps is co-NP-complete already for τ=2. On the other hand, for chordal and P5-free graphs, we prove that the problem is solvable in polynomial time. Finally, we show that the problem is fixed-parameter tractable parameterized by both the graph's neighborhood diversity and the number of steps τ.

Abstract. For a fixed finite collection of graphs [Formula: see text] the [Formula: see text]-M-Deletion problem is as follows: given an [Formula: see text]-vertex input graph [Formula: see text] find the minimum number of vertices that intersect all minor models in [Formula: see text] of the graphs in [Formula: see text]. by Courcelle’s Theorem, this problem can be solved in time [Formula: see text] where [Formula: see text] is the treewidth of [Formula: see text] for some function [Formula: see text] depending on [Formula: see text]. In a recent series of articles, we have initiated the program of optimizing asymptotically the function [Formula: see text]. Here we provide an algorithm showing that [Formula: see text] for every collection [Formula: see text]. Prior to this work, the best known function [Formula: see text] was double-exponential in [Formula: see text]. In particular, our algorithm vastly extends the results of Jansen, Lokshtanov, and Saurabh [ Proc. of the 25 th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2014, pp. 1802–1811] for the particular case [Formula: see text] and of Kociumaka and Pilipczuk [ Algorithmica, 81 (2019), pp. 3655–3691] for graphs of bounded genus, and answers an open problem posed by Cygan et al. [ Inform. Comput., 256 (2017), pp. 62–82]. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. Together with our previous results providing single-exponential algorithms for particular collections [Formula: see text] [J. Baste, I. Sau, and D. M. Thilikos, Theoret. Comput. Sci., 814 (2020), pp. 135–152] and general lower bounds [J. Baste, I. Sau, and D. M. Thilikos, J. Comput. Syst. Sci., 109 (2020), pp. 56–77], our algorithm yields the following complexity dichotomy when [Formula: see text] contains a single connected graph [Formula: see text] assuming the Exponential Time Hypothesis: [Formula: see text] if [Formula: see text] is a contraction of the chair or the banner , and [Formula: see text] otherwise.

Abstract. A linkage in a graph [Formula: see text] of size [Formula: see text] is a subgraph [Formula: see text] of [Formula: see text] whose connected components are [Formula: see text] paths. The pattern of a linkage of size [Formula: see text] is the set of [Formula: see text] pairs formed by the endpoints of these paths. A consequence of the Unique Linkage Theorem is the following: there exists a function [Formula: see text] such that if a plane graph [Formula: see text] contains a sequence [Formula: see text] of at least [Formula: see text] nested cycles and a linkage of size at most [Formula: see text] whose pattern vertices lay outside the outer cycle of [Formula: see text] then [Formula: see text] contains a linkage with the same pattern avoiding the inner cycle of [Formula: see text]. In this paper we prove the following variant of this result: Assume that all the cycles in [Formula: see text] are “orthogonally” traversed by a linkage [Formula: see text] and [Formula: see text] is a linkage whose pattern vertices may lay either outside the outer cycle or inside the inner cycle of [Formula: see text]. We prove that there are two functions [Formula: see text], such that if [Formula: see text] has size at most [Formula: see text], [Formula: see text] has size at least [Formula: see text] and [Formula: see text], then there is a linkage with the same pattern as [Formula: see text] that is “internally combed” by [Formula: see text], in the sense that [Formula: see text]. This result applies to any graph that is partially embedded on a disk (where [Formula: see text] is also embedded). In fact, we prove this result in the most general version where the linkage [Formula: see text] is [Formula: see text]-scattered: every two vertices of distinct paths are within a distance bigger than [Formula: see text]. We deduce several variants of this result in the cases where [Formula: see text] and [Formula: see text]. These variants permit the application of the Unique Linkage Theorem on several path routing problems on embedded graphs.

For a finite collection of graphs ℱ, the ℱ- TM-Deletion problem has as input an n -vertex graph G and an integer k and asks whether there exists a set S ⊆ V(G) with |S| ≤ k such that G \ S does not contain any of the graphs in ℱ as a topological minor. We prove that for every such ℱ, ℱ - TM-Deletion is fixed parameter tractable on planar graphs. Our algorithm runs in a 2 𝒪( k 2) ⋅ n 2 time, or, alternatively, in 2 𝒪( k ) ⋅ n 4 time. Our techniques can easily be extended to graphs that are embeddable on any fixed surface.

We provide a “vortex-free” refinement of the seminal structure theorem for $K_{t} -$minor free graphs by Robertson and Seymour as follows: we identify a (parameterized) graph Htand we prove that if we replace Ktby Ht, then the resulting decomposition becomes “vortex-free”. Up to now, the most general classes of graphs admitting such a result were either bounded Euler genus graphs or the single-crossing minor-free graphs. This result is tight in the sense that, whenever we minor-exclude a graph that is not a minor of some Ht, the appearance of vortices is unavoidable. Using the above decomposition theorem, we design an algorithm that, given an $H_{t} -$minor-free graph G, computes the generating function of all perfect matchings of G in polynomial time. This algorithm yields, on $H_{t} -$minor-free graphs, polynomial algorithms for computational problems such as the dimer problem, the exact matching problem, and the computation of the permanent. Our results, combined with known complexity results, imply a complete characterization of minor-closed graph classes where the number of perfect matchings is polynomially computable: They are precisely those graph classes that do not contain every Htas a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes.

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 (represented by a graph) 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 are 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 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 Rzaͅżewski [ Theoret. Comput. Sci., 794 (2019), pp. 85--100]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced by Bodlaender and Kloks [ J. Algorithms, 21 (1996), pp. 358--402] for the design of linear parameterized algorithms for treewidth and pathwidth. While this technique has been later applied to other parameters, none of its advancements was able to deal with the connectivity demand, as it is a “global” demand that concerns an unbounded number of parts of the graph of unbounded size. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted to deliver linear parameterized algorithms for the connected variants of other width parameters as well. An immediate consequence of our result is a $2^{O(k^2)}\cdot n$ time algorithm for the monotone and connected version of the edge search number.

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

The elimination distance to some target graph property P is a general graph modification parameter introduced by Bulian and Dawar. We initiate the study of elimination distances to graph properties expressible in first-order logic. We delimit the problem’s fixed-parameter tractability by identifying sufficient and necessary conditions on the structure of prefixes of first-order logic formulas. Our main result is the following meta-theorem: For every graph property P expressible by a first order-logic formula \( \varphi \in \Sigma _3 \) , that is, of the form \( \begin{equation*} \varphi =\exists x_1\exists x_2\cdots \exists x_r\ \ \forall y_{1}\forall y_{2}\cdots \forall y_{s}\ \ \exists z_1\exists z_2\cdots \exists z_t~~ \psi ,\end{equation*} \) where \( \psi \) is a quantifier-free first-order formula, checking whether the elimination distance of a graph to P does not exceed \( k \) , is fixed-parameter tractable parameterized by \( k \) . Properties of graphs expressible by formulas from \( \Sigma _3 \) include being of bounded degree, excluding a forbidden subgraph, or containing a bounded dominating set. We complement this theorem by showing that such a general statement does not hold for formulas with even slightly more expressive prefix structure: There are formulas \( \varphi \in \Pi _3 \) , for which computing elimination distance is \( {\sf W}[2] \) -hard.

The elimination distance to some target graph propertyPis a general graph modification parameter introduced by Bulian and Dawar. We initiate the study of elimination distances to graph properties expressible in first-order logic. We delimit the problem's fixed-parameter tractability by identifying sufficient and necessary conditions on the structure of prefixes of first-order logic formulas. Our main result is the following meta-theorem: For every graph propertyPexpressible by a first order-logic formula φ ∈ Σ3, that is, of the form φ = ∃x1∃x2⋯∃xr∀y1∀y2⋯∀ys∃z1∃z2⋯∃ztψ, where ψ is a quantifier-free first-order formula, checking whether the elimination distance of a graph toPdoes not exceed k, is fixed-parameter tractable parameterized by k. Properties of graphs expressible by formulas from Σ3 include being of bounded degree, excluding a forbidden subgraph, or containing a bounded dominating set. We complement this theorem by showing that such a general statement does not hold for formulas with even slightly more expressive prefix structure: There are formulas φ ∈ Π3, for which computing elimination distance is W[2]-hard.

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. [ Proceedings of FOCS, IEEE, 2012, pp. 470--479], 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 $\mathcal{O}(m^3 \cdot n^3 \cdot \log m)$, a linear kernel that can be computed in time $\mathcal{O}(m^4 \cdot n^3 \cdot \log m)$, and a $\mathcal{O}(2^{\mathcal{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., 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. [ ACM Trans. Algorithms, 13 (2017), p. 35]. This reveals that the kernelization complexity of $\mathcal{F}$-Immersion Deletion is quite different from that of $\mathcal{F}$-Minor Deletion.

In general, a graph modification problem is defined by a graph modification operation ⊠ and a target graph property 𝒫. Typically, the modification operation ⊠ may be vertex removal, edge removal, edge contraction, or edge addition and the question is, given a graph G and an integer k, whether it is possible to transform G to a graph in 𝒫 after applying k times the operation ⊠ on G. This problem has been extensively studied for particilar instantiations of ⊠ and 𝒫. In this paper we consider the general property 𝒫_ϕ of being planar and, moreover, being a model of some First-Order Logic sentence ϕ (an FOL-sentence). We call the corresponding meta-problem Graph ⊠-Modification to Planarity and ϕ and prove the following algorithmic meta-theorem: there exists a function f: ℕ² → ℕ such that, for every ⊠ and every FOL sentence ϕ, the Graph ⊠-Modification to Planarity and ϕ is solvable in f(k,|ϕ|)⋅n² time. The proof constitutes a hybrid of two different classic techniques in graph algorithms. The first is the irrelevant vertex technique that is typically used in the context of Graph Minors and deals with properties such as planarity or surface-embeddability (that are not FOL-expressible) and the second is the use of Gaifman’s Locality Theorem that is the theoretical base for the meta-algorithmic study of FOL-expressible problems.

Let G be a graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G⧵S belongs to G. We prove that if G is minor-closed, then there is an algorithm that either returns a set S certifying that G is a k-apex of G or reports that such a set does not exist, in 2^{poly(k)}n³ time. Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of G, i.e., the minor-minimal set of graphs not belonging to G. In the special case where G excludes some apex graph as a minor, we give an alternative algorithm running in 2^{poly(k)}n² time.

Neural networks have become a very popular tool for many machine learning tasks, 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.

For a fixed connected graph H, the {H}-M-Deletion problem asks, given a graph G, for the minimum number of vertices that intersect all minor models of H in G. It is known that this problem can be solved in time f (tw) · n(1), where tw is the treewidth of G. We determine the asymptotically optimal function f(tw), for each possible choice of H. Namely, we prove that, under the ETH, f(tw) = 2Θ(tw) if H is a contraction of the chair or the banner, and f (tw) = 2Θ(tw·log tw) otherwise. Prior to this work, such a complete characterization was only known when H is a planar graph with at most five vertices. For the upper bounds, we present an algorithm in time 2Θ(tw·log tw)·n(1) for the more general problem where all minor models of connected graphs in a finite family need to be hit. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, Bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. In particular, this algorithm vastly generalizes a result of Jansen et al. [SODA 2014] for the particular case = {K5, K3,3}. For the lower bounds, our reductions are based on a generic construction building on the one given by the authors in [IPEC 2018], which uses the framework introduced by Lokshtanov et al. [SODA 2011] to obtain superexponential lower bounds.

For a finite collection of graphs , the -TM-Deletion problem has as input an n-vertex graph G and an integer k and asks whether there exists a set S ⊆ V(G) with |S| ≤ k such that G\S does not contain any of the graphs in as a topological minor. We prove that for every such , -TM-Deletion is fixed parameter tractable on planar graphs. In particular, we provide an f(h, k) · n2 algorithm where h is an upper bound to the vertices of the graphs in .

Abstract A subgraph 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 $${\mathscr {G}}$$ G , is there a subgraph complement of G which is in $${\mathscr {G}}$$ G ? We show that this problem can be solved in polynomial time for various choices of the graphs class $${\mathscr {G}}$$ G , such as bipartite, d-degenerate, or cographs. We complement these results by proving that the problem is $${{\mathrm{NP}}}$$ NP -complete when $${\mathscr {G}}$$ G is the class of regular graphs.

Abstract We study the minimum diameter spanning tree problem under the reload cost model (Diameter‐Treefor short) introduced by Wirth and Steffan. In this problem, given an undirected edge‐colored graphG, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree ofGof minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of theDiameter‐Treeproblem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree Δ of the input graph. We prove thatDiameter‐Treeispara‐NP‐hard for any combination of two of these three parameters, and that it isFPTparameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we proveDiameter‐Treeto beNP‐hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan proved that the problem can be solved in polynomial time on graphs with Δ = 3, and Galbiati proved that it isNP‐hard if Δ = 4. Our results show, in particular, that without the requirement of the triangle inequality, the problem isNP‐hard if Δ = 3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove thatDiameter‐Treeis inXPandW[1]‐hard parameterized by the treewidth plus Δ.

Bidimensionality theory was introduced by [E. D. Demaine et al., J. ACM, 52 (2005), pp. 866--893] as a tool to obtain subexponential 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, Philadelphia, 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 (resp., 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 (resp., an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems admit linear kernels on the corresponding graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work.

For a finite collection of graphs ${\cal F}$, the $\mathcal{F}$-M-Deletion problem consists in, given a graph $G$ and an integer $k$, deciding whether there exists $S \subseteq V(G)$ with $|S| \leq k$ such that $G \setminus S$ does not contain any of the graphs in ${\cal F}$ as a minor. We are interested in the parameterized complexity of $\mathcal{F}$-M-Deletion when the parameter is the treewidth of $G$, denoted by ${tw}$. Our objective is to determine, for a fixed ${\cal F}$, the smallest function $f_{{\cal F}}$ such that $\mathcal{F}$-M-Deletion can be solved in time $f_{{\cal F}}({tw}) \cdot n^{\mathcal{O}(1)}$ on $n$-vertex graphs. We prove that $f_{{\cal F}}({tw}) = 2^{2^{\mathcal{O} ({tw} \cdot\log {tw})}}$ for every collection ${\cal F}$, that $f_{{\cal F}}({tw}) = 2^{\mathcal{O} ({tw} \cdot\log {tw})}$ if ${\cal F}$ contains a planar graph, and that $f_{{\cal F}}({tw}) = 2^{\mathcal{O} ({tw})}$ if in addition the input graph $G$ is planar or embedded in a surface. We also consider the version of the problem where the graphs in ${\cal F}$ are forbidden as topological minors, called $\mathcal{F}$-TM-Deletion. We prove similar results for this problem, except that in the last two algorithms, instead of requiring $\mathcal{F}$ to contain a planar graph, we need it to contain a subcubic planar graph. This is the first of a series of articles on this topic.

The node search game against a lazy (or, respectively, agile) invisible robber has been introduced as a search-game analogue of the treewidth parameter (and, respectively, pathwidth). In the connected variants of the above two games, we additionally demand that, at each moment of the search, the clean territories are connected. The connected search game against an agile and invisible robber has been extensively examined. The monotone variant (where we also demand that the clean territories are progressively increasing) of this game, corresponds to the graph parameter of connected pathwidth. It is known that the price of connectivty to search for an agile robber is bounded by 2, that is the connected pathwidth of a graph is at most twice (plus some constant) its pathwidth. In this paper, we investigate the connected search game against a lazy robber. A lazy robber moves only when the searchers' strategy threatens the location that he currently occupies. We introduce two alternative graph-theoretic formulations of this game, one in terms of connected tree decompositions, and one in terms of (connected) layouts, leading to the graph parameter of connected treewidth. We observe that connected treewidth parameter is closed under contractions and prove that for every k >= 2, the set of contraction obstructions of the class of graphs with connected treewidth at most k is infinite. Our main result is a complete characterization of the obstruction set for k=2. One may observe that, so far, only a few complete obstruction sets are explicitly known for contraction closed graph classes. We finally show that, in contrast to the agile robber game, the price of connectivity is unbounded.

We define a general variant of the graph clustering problem where the criterion of density for the clusters is (high) connectivity. In Clustering to Given Connectivities, we are given an n-vertex graph G, an integer k, and a sequence Lambda= of positive integers and we ask whether it is possible to remove at most k edges from G such that the resulting connected components are exactly t and their corresponding edge connectivities are lower-bounded by the numbers in Lambda. We prove that this problem, parameterized by k, is fixed parameter tractable, i.e., can be solved by an f(k)* n^{O(1)}-step algorithm, for some function f that depends only on the parameter k. Our algorithm uses the recursive understanding technique that is especially adapted so to deal with the fact that we do not impose any restriction to the connectivity demands in Lambda.

A replacement action is a function L that maps each k-vertex labeled graph to another k-vertex graph. We consider a general family of graph modification problems, called L-Replacement to C, where the input is a graph G and the question is whether it is possible to replace in G some k-vertex subgraph H of it by L(H) so that the new graph belongs to the graph class C. L-Replacement to C can simulate several modification operations such as edge addition, edge removal, edge editing, and diverse completion and superposition operations. In this paper, we prove that for any action L, if C is the class of planar graphs, there is an algorithm that solves L-Replacement to C in O(|G|^{2}) steps. We also present several applications of our approach to related problems.

The notion of tree-cut width has been introduced by Wollan in [The structure of graphs not admitting a fixed immersion, Journal of Combinatorial Theory, Series B, 110:47 - 66, 2015]. It is defined via tree-cut decompositions, which are tree-like decompositions that highlight small (edge) cuts in a graph. In that sense, tree-cut decompositions can be seen as an edge-version of tree-decompositions and have algorithmic applications on problems that remain intractable on graphs of bounded treewidth. In this paper, we prove that every graph admits an optimal tree-cut decomposition that satisfies a certain Menger-like condition similar to that of the lean tree decompositions of Thomas [A Menger-like property of tree-width: The finite case, Journal of Combinatorial Theory, Series B, 48(1):67 - 76, 1990]. This allows us to give, for every k in N, an upper-bound on the number immersion-minimal graphs of tree-cut width k. Our results imply the constructive existence of a linear FPT-algorithm for tree-cut width.

Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most k are closed under taking immersions, the results of Robertson and Seymour imply that there is a finite list of minimal immersion obstructions for admitting a cut layout of width at most k. We prove that every minimal immersion obstruction for cutwidth at most k has size at most $$2^{{O}(k^3\log k)}$$ . As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time $$2^{{O}(k^2\log k)}\cdot n$$ , where k is the optimum width and n is the number of vertices. While being slower by a $$\log k$$ -factor in the exponent than the fastest known algorithm, given by Thilikos et al. (J Algorithms 56(1):1–24, 2005; J Algorithms 56(1):25–49, 2005), our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts.

We study the concept of compactor, which may be seen as a counting-analogue of kernelization in counting parameterized complexity. For a function F:Sigma^* -> N and a parameterization kappa: Sigma^* -> N, a compactor (P,M) consists of a polynomial-time computable function P, called condenser, and a computable function M, called extractor, such that F=M o P, and the condensing P(x) of x has length at most s(kappa(x)), for any input x in Sigma^*. If s is a polynomial function, then the compactor is said to be of polynomial-size. Although the study on counting-analogue of kernelization is not unprecedented, it has received little attention so far. We study a family of vertex-certified counting problems on graphs that are MSOL-expressible; that is, for an MSOL-formula phi with one free set variable to be interpreted as a vertex subset, we want to count all A subseteq V(G) where |A|=k and (G,A) models phi. In this paper, we prove that every vertex-certified counting problems on graphs that is MSOL-expressible and treewidth modulable, when parameterized by k, admits a polynomial-size compactor on H-topological-minor-free graphs with condensing time O(k^2n^2) and decoding time 2^{O(k)}. This implies the existence of an FPT-algorithm of running time O(n^2 k^2)+2^{O(k)}. All aforementioned complexities are under the Uniform Cost Measure (UCM) model where numbers can be stored in constant space and arithmetic operations can be done in constant time.

Given two graphs G and H, we define $$\mathsf{v}\hbox {-}\mathsf{cover}_{H}(G)$$ (resp. $$\mathsf{e}\hbox {-}\mathsf{cover}_{H}(G)$$ ) as the minimum number of vertices (resp. edges) whose removal from G produces a graph without any minor isomorphic to H. Also $$\mathsf{v}\hbox {-}\mathsf{pack}_{H}(G)$$ (resp. $$\mathsf{e}\hbox {-}\mathsf{pack}_{H}(G)$$ ) is the maximum number of vertex- (resp. edge-) disjoint subgraphs of G that contain a minor isomorphic to H. We denote by $$\theta _{r}$$ the graph with two vertices and r parallel edges between them. When $$H=\theta _{r}$$ , the parameters $$\mathsf{v}\hbox {-}\mathsf{cover}_{H}$$ , $$\mathsf{e}\hbox {-}\mathsf{cover}_{H}$$ , $$\mathsf{v}\hbox {-}\mathsf{pack}_{H}$$ , and $$\mathsf{e}\hbox {-}\mathsf{pack}_{H}$$ are NP-hard to compute (for sufficiently big values of r). Drawing upon combinatorial results in Chatzidimitriou et al. (Minors in graphs of large $$\theta _r$$ -girth, 2015, arXiv:1510.03041 ), we give an algorithmic proof that if $$\mathsf{v}\hbox {-}\mathsf{pack}_{{\theta _{r}}}(G)\le k$$ , then $$\mathsf{v}\hbox {-}\mathsf{cover}_{\theta _{r}}(G) = O(k\log k)$$ , and similarly for $$\mathsf{e}\hbox {-}\mathsf{pack}_{\theta _{r}}$$ and $$\mathsf{e}\hbox {-}\mathsf{cover}_{\theta _{r}}$$ . In other words, the class of graphs containing $${\theta _{r}}$$ as a minor has the vertex/edge Erdős–Pósa property, for every positive integer r. Using the algorithmic machinery of our proofs we introduce a unified approach for the design of an $$O(\log \mathrm{OPT})$$ -approximation algorithm for $$\mathsf{v}\hbox {-}\mathsf{pack}_{{\theta _{r}}}$$ , $$\mathsf{v}\hbox {-}\mathsf{cover}_{{\theta _{r}}}$$ , $$\mathsf{e}\hbox {-}\mathsf{pack}_{{\theta _{r}}}$$ , and $$\mathsf{e}\hbox {-}\mathsf{cover}_{{\theta _{r}}}$$ that runs in $$O(n\cdot \log (n)\cdot m)$$ steps. Also, we derive several new Erdős–Pósa-type results from the techniques that we introduce.

We initiate the algorithmic study of the following “structured augmentation” question: is it possible to increase the connectivity of a given graph $G$ by superposing it with another given graph $H$? More precisely, graph $F$ is the superposition of $G$ and $H$ with respect to injective mapping $\varphi\colon V(H)\rightarrow V(G)$ if every edge $uv$ of $F$ is either an edge of $G$ or $\varphi^{-1}(u)\varphi^{-1}(v)$ is an edge of $H.$ Thus $F$ contains both $G$ and $H$ as subgraphs, and the edge set of $F$ is the union of the edge sets of $G$ and $\varphi(H).$ We consider the following optimization problem. Given graphs $G,$ $H,$ and a weight function $\omega$ assigning nonnegative weights to pairs of vertices of $V(G),$ the task is to find $\varphi$ of minimum weight $\omega(\varphi)= \sum_{xy\in E(H)}\omega(\varphi(x)\varphi(y))$ such that the edge connectivity of the superposition $F$ of $G$ and $H$ with respect to $\varphi$ is higher than the edge connectivity of $G$. Our main result is the following “dichotomy” complexity classification. We say that a class of graphs $\mathcal{C}$ has bounded vertex-cover number if there is a constant $t$ depending on $\mathcal{C}$ only such that the vertex-cover number of every graph from $\mathcal{C}$ does not exceed $t.$ We show that for every class of graphs $\mathcal{C}$ with bounded vertex-cover number, the problems of superposing into a connected graph $F$ and to 2-edge connected graph $F$ are solvable in polynomial time when $H\in\mathcal{C}.$ On the other hand, for any hereditary class $\mathcal{C}$ with unbounded vertex-cover number, both problems are NP-hard when $H\in\mathcal{C}.$ For the unweighted variants of structured augmentation problems, i.e., the problems where the task is to identify whether there is a superposition of graphs of required connectivity, we provide necessary and sufficient combinatorial conditions on the existence of such superpositions. These conditions imply polynomial time algorithms solving the unweighted variants of the problems.

We give the first linear kernels for the D ominating S et and C onnected D ominating S et problems on graphs excluding a fixed graph H as a topological minor. In other words, we prove the existence of polynomial time algorithms that, for a given H -topological-minor-free graph G and a positive integer k , output an H -topological-minor-free graph G ′ on O ( k ) vertices such that G has a (connected) dominating set of size k if and only if G ′ has one. Our results extend the known classes of graphs on which the D ominating S et and C onnected D ominating S et problems admit linear kernels. Prior to our work, it was known that these problems admit linear kernels on graphs excluding a fixed apex graph H as a minor. Moreover, for D ominating S et , a kernel of size k c ( H ) , where c ( H ) is a constant depending on the size of H , follows from a more general result on the kernelization of D ominating S et on graphs of bounded degeneracy. Alon and Gutner explicitly asked whether one can obtain a linear kernel for D ominating S et on H -minor-free graphs. We answer this question in the affirmative and in fact prove a more general result. For C onnected D ominating S et no polynomial kernel even on H -minor-free graphs was known prior to our work. On the negative side, it is known that C onnected D ominating S et on 2-degenerated graphs does not admit a polynomial kernel unless coNP ⊆ NP/poly. Our kernelization algorithm is based on a non-trivial combination of the following ingredients • The structural theorem of Grohe and Marx [STOC 2012] for graphs excluding a fixed graph H as a topological minor; • A novel notion of protrusions, different than the one defined in [FOCS 2009]; • Our results are based on a generic reduction rule that produces an equivalent instance (in case the input graph is H -minor-free) of the problem, with treewidth O (√ k ). The application of this rule in a divide-and-conquer fashion, together with the new notion of protrusions, gives us the linear kernels. A protrusion in a graph [FOCS 2009] is a subgraph of constant treewidth which is separated from the rest of the graph by at most a constant number of vertices. In our variant of protrusions, instead of stipulating that the subgraph be of constant treewidth , we ask that it contains a constant number of vertices from a solution . We believe that this new take on protrusions would be useful for other graph problems and in different algorithmic settings.

We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirected edge-colored graph G, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree of G of minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of the DIAMETER-TREE problem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree Delta of the input graph. We prove that DIAMETER-TREE is para-np-hard for any combination of two of these three parameters, and that it is FPT parameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we prove DIAMETER-TREE to be NP-hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan (2001) proved that the problem can be solved in polynomial time on graphs with Delta=3, and Galbiati (2008) proved that it is NP-hard if Delta=4. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP-hard if Delta=3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove that DIAMETER-TREE is in XP and W[1]-hard parameterized by the treewidth plus Delta.

For a fixed collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, decide whether there exists a subset S of V(G) of size at most k such that G-S does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of F-M-DELETION when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F}, the smallest function f_F such that F-M-DELETION can be solved in time f_F(tw)n^{O(1)} on n-vertex graphs. Using and enhancing the machinery of boundaried graphs and small sets of representatives introduced by Bodlaender et al. [J ACM, 2016], we prove that when all the graphs in F are connected and at least one of them is planar, then f_F(w) = 2^{O(wlog w)}. When F is a singleton containing a clique, a cycle, or a path on i vertices, we prove the following asymptotically tight bounds: - f_{K_4}(w) = 2^{Theta(wlog w)}. - f_{C_i}(w) = 2^{Theta(w)} for every i<5, and f_{C_i}(w) = 2^{Theta(wlog w)} for every i>4. - f_{P_i}(w) = 2^{Theta(w)} for every i<5, and f_{P_i}(w) = 2^{Theta(wlog w)} for every i>5. The lower bounds hold unless the Exponential Time Hypothesis fails, and the superexponential ones are inspired by a reduction of Marcin Pilipczuk [Discrete Appl Math, 2016]. The single-exponential algorithms use, in particular, the rank-based approach introduced by Bodlaender et al. [Inform Comput, 2015]. We also consider the version of the problem where the graphs in F are forbidden as topological minors, and prove essentially the same set of results holds.

Given a graph G, we define bcg(G) as the minimum k for which G can be contracted to the uniformly triangulated grid Gamma_k. A graph class G has the SQGC property if every graph G in G has treewidth O(bcg(G)c) for some 1 <= c < 2. The SQGC 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 general family of graph classes that satisfy the SQGC property and includes bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for several intersection graph classes of 2-dimensional geometrical objects.

We consider the following graph modification problem. Let the input consist of a graph G = ( V , E ) , a weight function w : V ∪ E → N , a cost function c : V ∪ E → N 0 and a degree function δ : V → 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 .

The Plane Subgraph (resp. Topological Minor) Completion problem asks, given a (possibly disconnected) plane (multi)graph Gamma and a connected plane (multi)graph Delta, whether it is possible to add edges in Gamma without violating the planarity of its embedding so that it contains some subgraph (resp. topological minor) that is topologically isomorphic to Delta. We give FPT algorithms that solve both problems in f(|E(Delta)|)*|E(\Gamma)|^{2} steps. Moreover, for the Plane Subgraph Completion problem we show that f(k)=2^{O(k*log(k))}.

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 kernelization. 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.

The problem of finding a disconnected cut in a graph is NP‐hard in general but polynomial‐time solvable on planar graphs. The problem of finding a minimal disconnected cut is also NP‐hard but its computational complexity was not known for planar graphs. We show that it is polynomial‐time solvable on 3‐connected planar graphs but NP‐hard for 2‐connected planar graphs. Our technique for the first result is based on a structural characterization of minimal disconnected cuts in 3‐connected ‐free‐minor graphs and on solving a topological minor problem in the dual. In addition we show that the problem of finding a minimal connected cut of size at least 3 is NP‐hard for 2‐connected apex graphs. Finally, we relax the notion of minimality and prove that the problem of finding a so‐called semi‐minimal disconnected cut is still polynomial‐time solvable on planar graphs. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(4), 250–259 2016

In this paper we design FPT-algorithms for two parameterized problems. The first is 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 Multiway Cut, namely Min-Max Multiway Cut: given a graph G, a non-negative integer l, 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 l edges with only one endpoint in this part. We parameterize 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(l * log(h) + l^{2 * log(l)}} * n^{4} * log(n) algorithm, where h is the order of the host graph H.We also prove that Min-Max Multiway Cut can be solved in time 2^{O((l * r)^2 * log(l *r))} * n^{4} * log(n). Our approach introduces a general problem, called List Allocation, whose expressive power permits the design of parameterized reductions of both aforementioned problems to it. Then our results are based on an FPT-algorithm for the List Allocation problem that is designed using a suitable adaptation of the randomized contractions technique (introduced by [Chitnis, Cygan, Hajiaghayi, Pilipczuk, and Pilipczuk, FOCS 2012]).

The 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 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)}} * n steps.

We provide an exposition of the main results of the theory of bidimensionality in parameterized algorithm design. This theory applies to graph problems that are bidimensional in the sense that i) their solution value is not increasing when we take minors or contractions of the input graph and ii) their solution value for the (triangulated) (k x k)-grid graph grows as a quadratic function of k. Under certain additional conditions, mainly of logical and combinatorial nature, such problems admit subexponential parameterized algorithms and linear kernels when their inputs are restricted to certain topologically defined graph classes. We provide all formal definitions and concepts in order to present these results in a rigorous way and in their latest update.

Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result of Bodlaender et al. [(Meta) kernelization, in Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2009, pp. 629--638] on graphs of bounded genus, then generalized by Fomin et al. [Bidimensionality and kernels, in Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadephia, 2010, pp. 503--510] to graphs excluding a fixed minor, and by Kim et al. [Linear kernels and single-exponential algorithms via protrusion decompositions, in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Comput. Sci., 7965 (2013), pp. 613--624] 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 counting monadic second order 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.

Graph clustering or community detection constitutes an important task forinvestigating the internal structure of graphs, with a plethora of applications in several domains. Traditional tools for graph clustering, such asspectral methods, typically suffer from high time and space complexity. In thisarticle, we present CoreCluster, an efficient graph clusteringframework based on the concept of graph degeneracy, that can be used along withany known graph clustering algorithm. Our approach capitalizes on processing thegraph in a hierarchical manner provided by its core expansion sequence, anordered partition of the graph into different levels according to the k-coredecomposition. Such a partition provides a way to process the graph inan incremental manner that preserves its clustering structure, whilemaking the execution of the chosen clustering algorithm much faster due to thesmaller size of the graph's partitions onto which the algorithm operates.

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 nonnegative integer $k,$ decide whether the cyclability of $G$ is at least $k,$ is NP-hard. We study the parametrized complexity of this problem. We prove that this problem, parameterized by $k,$ is ${\sf co{-}W[1]}$-hard and that it does not admit a polynomial kernel on planar graphs, unless ${NP}\subseteq{\sf co}{-}{NP}/{poly}$. On the positive side, we give an 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.

Lately, there has been an increased interest in signed networks with applications in trust, security, or social computing. This paper focuses on the issue of defining models and metrics for reciprocity in signed graphs. In unsigned directed networks, reciprocity quantifies the predisposition of network members in creating mutual connections. On the other hand, this concept has not yet been investigated in the case of signed graphs. We capitalize on the graph degeneracy concept to identify subgraphs of the signed network in which reciprocity is more likely to occur. This enables us to assess reciprocity at a global level, rather than at an exclusively local one as in existing approaches. The large scale experiments we perform on real world data sets of trust networks lead to both interesting and intuitive results. We believe these reciprocity measures can be used in various social applications such as trust management, community detection and evaluation of individual nodes. The global reciprocity we define in this paper is closely correlated to the clustering structure of the graph, more than the local reciprocity as it is indicated by the experimental evaluation we conducted.

Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result [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-F-Deletion on graphs excluding a fixed (topological) minor in the case where all the graphs in F are connected.

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, 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 noncrossing 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.

We give the first linear kernels for Dominating Set and Connected Dominating Set problems on graphs excluding a fixed graph H as a topological minor.

One of the major results of [N. Robertson and P. D. Seymour, Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B, 63 (1995), pp. 65--110], also known as the weak structure theorem, reveals the local structure of graphs excluding some graph as a minor: each such graph $G$ either has small treewidth or contains the subdivision of a planar graph (a wall) that can be arranged in a flat manner inside $G$, given that some small set of vertices is removed. We prove an optimized version of that theorem where (i) the relation between the treewidth of the graph and the height of the wall is linear (thus best possible) and (ii) the number of vertices to be removed is minimized.

We demonstrate a system that supports the visual exploration of collaboration networks. The system leverages the notion of fractional cores introduced in earlier work to rank vertices in a collaboration network and filter vertices' neighborhoods. Fractional cores build on the idea of graph degeneracy as captured by the notion of k-cores in graph theory and extend it to undirected edge-weighted graphs. In a co-authorship network, for instance, the fractional core index of an author intuitively reflects the degree of collaboration with equally or higher-ranked authors. Our system has been deployed on a real-world co-authorship network derived from DBLP, demonstrating that the idea of fractional cores can be applied even to large-scale networks. The system provides an easy-to-use interface to query for the fractional core index of an author, to see who the closest equally or higher-ranked co-authors are, and explore the entire co-authorship network in an incremental manner.

We give the first linear kernels for Dominating Set and Connected Dominating Set problems on graphs excluding a fixed graph H as a minor. In other words, we give polynomial time algorithms that, for a given H-minor free graph G and positive integer k, output an H-minor free graph G′ on O(k) vertices such that G has a (connected) dominating set of size k if and only if G′ has. Prior to our work, the only polynomial kernel for Dominating Set on graphs excluding a fixed graph H as a minor was due to Alon and Gutner [ECCC 2008, IWPEC 2009] and to Philip, Raman, and Sikdar [ESA 2009] but the size of their kernel is kc(H), where c(H) is a constant depending on the size of H. Alon and Gutner asked explicitly, whether one can obtain a linear kernel for Dominating Set on H-minor free graphs. We answer this question in affirmative. For Connected Dominating Set no polynomial kernel on H-minor free graphs was known prior to our work. Our results are based on a novel generic reduction rule producing an equivalent instance of the problem with treewidth O(√k). The application of this rule in a divide-and-conquer fashion together with protrusion techniques brings us to linear kernels. As a byproduct of our results we obtain the first subexponential time algorithms for Connected Dominating Set, a deterministic algorithm solving the problem on an n-vertex H-minor free graph in time 2O(√k log k) + nO(1) and a Monte Carlo algorithm of running time 2O(√k) + nO(1). For Dominating Set our results implies a significant simplification and refinement of a 2O(√k) nO(1) algorithm on H minor free graphs due to Demaine et al. [SODA 2003, J. ACM 2005].

The Contraction Checking problem asks, given two graphs H and G as input, whether H can be obtained from G by a sequence of edge contractions. Contraction Checking remains NP-complete, even when H is fixed. We show that this is not the case when G is embeddable in a surface of fixed Euler genus. In particular, we give an algorithm that solves Contraction Checking in f(h,g)*|V(G)|^3 steps, where h is the size of H and g is the Euler genus of the input graph G.

In this note, we give a proof that several vertex ordering problems can be solved in O ∗(2 n ) time and O ∗(2 n ) space, or in O ∗(4 n ) time and polynomial space. The algorithms generalize algorithms for the Travelling Salesman Problem by Held and Karp (J. Soc. Ind. Appl. Math. 10:196–210, 1962) and Gurevich and Shelah (SIAM J. Comput. 16:486–502, 1987). We survey a number of vertex ordering problems to which the results apply.

We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential-time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time O *(2 n ). This algorithm is based on the old dynamic programming method introduced by Held and Karp for the Traveling Salesman problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. We also consider the problem of computing Treewidth under the restriction that the space used is only polynomial and give a simple O *(4 n ) algorithm that requires polynomial space. We also show that with a more complicated algorithm using balanced separators, Treewidth can be computed in O *(2.9512 n ) time and polynomial space.

Community sub graphs are characterized by dense connections or interactions among its nodes. Community detection and evaluation is an important task in graph mining. A variety of measures have been proposed to evaluate the quality of such communities. In this paper, we evaluate communities based on the k-core concept, as means of evaluating their collaborative nature - a property not captured by the single node metrics or by the established community evaluation metrics. Based on the k-core, which essentially measures the robustness of a community under degeneracy, we extend it to weighted graphs, devising a novel concept of k-cores on weighted graphs. We applied the k-core approach on large real world graphs - such as DBLP and report interesting results.

Community detection and evaluation is an important task in graph mining. In many cases, a community is defined as a sub graph characterized by dense connections or interactions among its nodes. A large variety of measures have been proposed to evaluate the quality of such communities - in most cases ignoring the directed nature of edges. In this paper, we introduce novel metrics for evaluating the collaborative nature of directed graphs - a property not captured by the single node metrics or by other established community evaluation metrics. In order to accomplish this objective, we capitalize on the concept of graph degeneracy and define a novel D-core framework, extending the classic graph-theoretic notion of k-cores for undirected graphs to directed ones. Based on the D-core, which essentially can be seen as a measure of the robustness of a community under degeneracy, we devise a wealth of novel metrics used to evaluate graph collaboration features of directed graphs. We applied the D-core approach on large real-world graphs such as Wikipedia and DBLP and report interesting results at the graph as well at node level.

The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello in order to extend the concept of hypergraph acyclicity. These notions were further generalized by Grohe and Marx, who introduced the fractional hypertree width of a hypergraph. All these width parameters on hypergraphs are useful for extending the tractability of many problems in database theory and artificial intelligence. In this paper, we study the approximability of (generalized, fractional) hypertree width of sparse hypergraphs where the criterion of sparsity reflects the sparsity of their incidence graphs. Our first step is to prove that the (generalized, fractional) hypertree width of a hypergraph [Formula: see text] is constant factor sandwiched by the treewidth of its incidence graph when the incidence graph belongs to some apex-minor-free graph class (the family of apex-minor-free graph classes includes planar graphs and graphs of bounded genus). This determines the combinatorial borderline above in which the notion of (generalized, fractional) hypertree width becomes essentially more general than treewidth, justifying that way its functionality as a hypergraph acyclicity measure. While for more general sparse families of hypergraphs treewidth of incidence graphs and all hypertree width parameters may differ arbitrarily, there are sparse families where a constant factor approximation algorithm is possible. In particular, we give a constant factor approximation polynomial time algorithm for (generalized, fractional) hypertree width on hypergraphs whose incidence graphs belong to some [Formula: see text]-minor-free graph class.

Graph searching problems are described as games played on graphs, between a set of cops and a fugitive. Variants of the game restrict the abilities of the cops and the fugitive and the corresponding search numbers (the least number of cops that have a winning strategy) are related to several well-known parameters in graph theory. We study the case where the fugitive is visible (the cops’ strategy can take into account his current position) and lazy (he moves only when the cops move to his position). Our results are stated and proven in a general setting where the fugitive’s speed (i.e., the lengths of paths he can move along) can be unbounded or bounded by some constant. We give a min-max characterization of the corresponding parameters, which we show to be computable in polynomial time for fugitives with unbounded speed and speed at most 3 and to be nondeterministic polynomial-time complete (NP-complete) for all other finite speeds. This is in contrast to the other standard versions of the game, where the parameters corresponding to fugitives with unbounded speed are NP-complete. Several consequences of our results are also discussed.

Bidimensionality theory appears to be a powerful framework in the development of meta-algorithmic techniques. It was introduced by Demaine et al. [J. ACM 2005] as a tool to obtain sub-exponential time parameterized algorithms for bidimensional problems on H-minor free graphs. Demaine and Hajiaghayi [SODA 2005] extended the theory to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this paper, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In parameterized complexity, each problem instance comes with a parameter k and the parameterized problem is said to admit a linear kernel if there is a polynomial time algorithm, called a kernelization algorithm, that reduces the input instance to an equivalent instance (called kernel) with size linearly bounded by k. We show that “essentially” all bidimensional problems not only have sub-exponential time algorithms and PTASs but they also have linear kernels, affirmatively answering an open question from [J. ACM 2005] where the existence of linear kernels was conjectured for the first time. In particular, we prove that every minor (respectively contraction) bidimensional problem that satisfies the separation property and is of finite integer index, admits a linear kernel for classes of graphs that exclude a fixed graph (respectively an apex graph H) H as a minor. Recently, Bodlaender et al. [FOCS 2009] laid the foundation for obtaining meta-algorithmic results for kernelization and showed that various problems satisfying some logical and compactness properties have polynomial, even linear kernels on graphs of bounded genus. With the use of bidimensionality we are able to extend these results to minor-free and apex-minor-free graphs. Our results imply that a multitude of bidimensional problems, which include Dominating Set, Feedback Vertex Set, Edge Dominating Set, Vertex Cover, r-Dominating Set, Connected Dominating Set, Cycle Packing, Connected Vertex Cover, Almost Constant Treewidth, and various other vertex covering and packing problems, admit linear kernels on the corresponding graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work.

Polynomial time preprocessing to reduce instance size is one of the most commonly deployed heuristics to tackle computationally hard problems. 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, we can reduce the size of the instance I to a polynomial in k, while preserving the answer. In this paper, we show that all problems expressible in Counting Monadic Second Order Logic and satisfying a compactness 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 compactness condition admit a linear kernel on graphs of bounded genus. The study of kernels on planar graphs was initiated by a seminal paper of Alber, Fellows, and Niedermeier [J. ACM, 2004 ] who showed that Planar Dominating Set admits a linear kernel. Following this result, a multitude of problems have been shown to admit linear kernels on planar graphs by combining the ideas of Alber et al. with problem specific reduction rules. Our theorems unify and extend all previously known kernelization results for planar graph problems. Combining our theorems with the Erdos-Posa property we obtain various new results on linear kernels for a number of packing and covering problems.

The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello (PODS'99, PODS'01) in order to extend the concept of hypergraph acyclicity. These notions were further generalized by Grohe and Marx in SODA'06, who introduced the fractional hypertree width of a hypergraph. All these width parameters on hypergraphs are useful for extending tractability of many problems in database theory and artificial intelligence. Computing each of these width parameters is known to be an NP-hard problem. Moreover, the (generalized) hypertree width of an n-vertex hypergraph cannot be approximated within a logarithmic factor unless P=NP. In this paper, we study the approximability of (generalized, fractional) hyper treewidth of sparse hypergraphs where the criterion of sparsity reflects the sparsity of their incidence graphs. Our first step is to prove that the (generalized, fractional) hypertree width of a hypergraph is constant-factor sandwiched by the treewidth of its incidence graph, when the incidence graph belongs to some apex-minor-free graph class (the family of apex-minor-free graph classes includes planar graphs and graphs of bounded genus). This determines the combinatorial borderline above which the notion of (generalized, fractional) hypertree width becomes essentially more general than treewidth, justifying that way its functionality as a hypergraph acyclicity measure. While for more general sparse families of hypergraphs treewidth of incidence graphs and all hypertree width parameters may differ arbitrarily, there are sparse families where a constant factor approximation algorithm is possible. In particular, we give a constant factor approximation polynomial time algorithm for (generalized, fractional) hypertree width on hypergraphs whose incidence graphs belong to some H-minor-free graph class. This extends the results of Feige, Hajiaghayi, and Lee from STOC'05 on approximating treewidth of H-minor-free graphs.

We define helicopter cops and robber games with multiple robbers, extending previous research, which considered only the pursuit of a single robber. Our model is defined for robbers that are visible (their position in the graph is known to the cops) and active (they can move at any point in the game) but is easily adapted to other variants of the single-robber game that have been considered in the literature. We show that the game with many robbers is nonmonotone: that is, fewer cops are needed if the robbers are allowed to reoccupy positions that were previously unavailable to them. As the moves of the cops depend on the position of the visible robbers, strategies for such games should be interactive, but the game becomes, in a sense, less interactive as the initial number of robbers increases. We prove that the main parameter emerging from the game, which we denote $\mathbf{mvams}(G,r)$, captures a hierarchy of parameters between proper pathwidth and proper treewidth, and we completely characterize it for trees, extending analogous existing characterizations of the pathwidth of trees. Moreover, we prove an upper bound for $\mathbf{mvams}(G,r)$ on general graphs and show that this bound is reached by an infinite class of graphs. On the other hand, if we consider the robbers to be invisible and lazy, the resulting parameters collapse in all cases to either proper pathwidth or proper treewidth, giving a further case where the classical equivalence between visible, active robbers and invisible, lazy robbers does not hold.

We introduce a new approach to design parameterized algorithms on planar graphs which builds on the seminal results of Robertson and Seymour on graph minors. Graph minors provide a list of powerful theoretical results and tools. However, the widespread opinion in the graph algorithms community about this theory is that it is of mainly theoretical importance. In this paper we show how deep min-max and duality theorems from graph minors can be used to obtain exponential speed-up to many known practical algorithms for different domination problems. Our use of branch-width instead of the usual tree-width allows us to obtain much faster algorithms. By using this approach, we show that the k-dominating set problem on planar graphs can be solved in time O(2 15.13 \sqrt k + n 3 ).

Bidimensionality provides a tool for developing subexponential fixed-parameter algorithms for combinatorial optimization problems on graph families that exclude a minor. This paper extends the theory of bidimensionality for graphs of bounded genus (which is a minor-excluding family). Specifically we show that, for any problem whose solution value does not increase under contractions and whose solution value is large on a grid graph augmented by a bounded number of handles, the treewidth of any bounded-genus graph is at most a constant factor larger than the square root of the problem's solution value on that graph. Such bidimensional problems include vertex cover, feedback vertex set, minimum maximal matching, dominating set, edge dominating set, r-dominating set, connected dominating set, planar set cover, and diameter. On the algorithmic side, by showing that an augmented grid is the prototype bounded-genus graph, we generalize and simplify many existing algorithms for such problems in graph classes excluding a minor. On the combinatorial side, our result is a step toward a theory of graph contractions analogous to the seminal theory of graph minors by Robertson and Seymour.

We introduce a new framework for designing fixed-parameter algorithms with subexponential running time---2 O(√k) n O(1) . Our results apply to a broad family of graph problems, called bidimensional problems , which includes many domination and problems such as vertex cover, feedback vertex set, minimum maximal matching, dominating set, edge dominating set, disk dimension, and many others restricted to bounded-genus graphs (phrased as bipartite-graph problem ). Furthermore, it is fairly straightforward to prove that a problem is bidimensional. In particular, our framework includes, as special cases, all previously known problems to have such subexponential algorithms. Previously, these algorithms applied to planar graphs, single-crossing-minor-free graphs, and/or map graphs; we extend these results to apply to bounded-genus graphs as well. In a parallel development of combinatorial results, we establish an upper bound on the treewidth (or branchwidth) of a bounded-genus graph that excludes some planar graph H as a minor. This bound depends linearly on the size |V(H)| of the excluded graph H and the genus g(G) of the graph G , and applies and extends the graph-minors work of Robertson and Seymour.Building on these results, we develop subexponential fixed-parameter algorithms for dominating set, vertex cover, and set cover in any class of graphs excluding a fixed graph H as a minor. In particular, this general category of graphs includes planar graphs, bounded-genus graphs, single-crossing-minor-free graphs, and any class of graphs that is closed under taking minors. Specifically, the running time is 2 O(√k) n h , where h is a constant depending only on H , which is polynomial for k = O (log 2 n ). We introduce a general approach for developing algorithms on H -minor-free graphs, based on structural results about H -minor-free graphs at the heart of Robertson and Seymour's graph-minors work. We believe this approach opens the way to further development on problems in H -minor-free graphs.

The ( k , r )-center problem asks whether an input graph G has ≤ k vertices (called centers ) such that every vertex of G is within distance ≤ r from some center. In this article, we prove that the ( k , r )-center problem, parameterized by k and R , is fixed-parameter tractable (FPT) on planar graphs, i.e., it admits an algorithm of complexity f ( k , r ) n O (1) where the function f is independent of n . In particular, we show that f ( k,r ) = 2 O ( r log r ) √k , where the exponent of the exponential term grows sublinearly in the number of centers. Moreover, we prove that the same type of FPT algorithms can be designed for the more general class of map graphs introduced by Chen, Grigni, and Papadimitriou. Our results combine dynamic-programming algorithms for graphs of small branchwidth and a graph-theoretic result bounding this parameter in terms of k and r . Finally, a byproduct of our algorithm is the existence of a PTAS for the r -domination problem in both planar graphs and map graphs.Our approach builds on the seminal results of Robertson and Seymour on Graph Minors, and as a result is much more powerful than the previous machinery of Alber et al. for exponential speedup on planar graphs. To demonstrate the versatility of our results, we show how our algorithms can be extended to general parameters that are “large” on grids. In addition, our use of branchwidth instead of the usual treewidth allows us to obtain much faster algorithms, and requires more complicated dynamic programming than the standard leaf/introduce/forget/join structure of nice tree decompositions. Our results are also unique in that they apply to classes of graphs that are not minor-closed, namely, constant powers of planar graphs and map graphs.

For several graph-theoretic parameters such as vertex cover and dominating set, it is known that if their sizes are bounded by k, then the treewidth of the graph is bounded by some function of k. This fact is used as the main tool for the design of several fixed-parameter algorithms on minor-closed graph classes such as planar graphs, single-crossing-minor-free graphs, and graphs of bounded genus. In this paper we examine whether similar bounds can be obtained for larger minor-closed graph classes and for general families of graph parameters, including all those for which such behavior has been reported so far. Given a graph parameter P, we say that a graph family $\mathcal{F}$ has the parameter-treewidth property for P if there is an increasing function t such that every graph $G\in\mathcal{F}$ has treewidth at most t(P(G)). We prove as our main result that, for a large family of graph parameters called contraction-bidimensional, a minor-closed graph family $\mathcal{F}$ has the parameter-treewidth property if $\mathcal{F}$ has bounded local treewidth. We also show "if and only if" for some graph parameters, and thus, this result is in some sense tight. In addition we show that, for a slightly smaller family of graph parameters called minor-bidimensional, all minor-closed graph families $\mathcal{F}$, excluding some fixed graphs, have the parameter-treewidth property. The contraction-bidimensional parameters include many domination and covering graph parameters such as vertex cover, feedback vertex set, dominating set, edge-dominating set, and q-dominating set (for fixed q). We use our theorems to develop new fixed-parameter algorithms in these contexts.

In this paper, we analyze the stability properties of the FIFO protocol in the Adversarial Queueing model for packet routing. We show a graph for which FIFO is stable for any adversary with injection rate r ≰ 0.1428. We generalize this results to show upper bound for stability of any network under FIFO protocol, answering partially an open question raised by Andrews et al. in [2]. We also design a network and an adversary for which FIFO is non-stable for any r ≱ 0.8357, improving the previous known bounds of [2].

The linkage of a graph is defined to be the maximum mm-degree of any of its subgraphs It is known that the linkage of a graph is equal to its width: for an arbitrary linear ordering of the vertices of the graph, consider the maximum, with respect to any vertex v, of the number of vertices connected with v and preceding it in the ordering; the width of the graph is the minimum of these maxima over all possible linear orderings. Width has been used in artificial intelligence in the context of constraint satisfaction problems (CSPs). A more general notion is defined by considering not the number of vertices preceding and connected with v but rather the least number of vertices preceding and connected with any cluster of at most j consecutive vertices extending to the right up to v (j is a given integer). The graph parameter thus defined is called j-width. No efficient algorithm was known for computing the j-width. In this paper, we introduce a graph parameter depending on j that refers to the subgraphs of the graph and generalizes the notion of linkage. We prove the min–max theorem that this graph parameter, which we call j-linkage, is equal to j-width, and we then give a polynomial-time algorithm for computing it (for constant j). We also find tight lower and upper bounds for the j-linkage (equivalently, the j-width) of graphs with given numbers of vertices and edges. It is interesting to note that a lower bound for the width of a graph had been found by Erdös; as we show, however, that bound is not tight. Moreover, we prove that our lower bound for width is also a tight lower bound for treewidth, pathwidth, and bandwidth, graph parameters that may be arbitrarily larger than width. Finally, we show that computing the j-linkage is a P-complete problem, whereas we prove that approximating it is a threshold problem: it is in NC for approximation factors $ < {1 / {(2j)}}$, and it is P-complete for approximation factors $ > {1 / 2}$.