Search

We introduce a graph-parametric framework for obtaining obstruction characterizations of graph parameters with respect to partial ordering relations. For this, we define the notions of class obstruction, parametric obstruction, and universal obstruction as combinatorial objects that determine the asymptotic behavior of graph parameters. Our framework permits a unified framework for classifying graph parameters. Under this framework, we survey existing graph- theoretic results on most known graph parameters. Also we provide some unifying results on their classification.

The \textsl{branchwidth} of a graph has been introduced by Roberson and Seymour as a measure of the tree-decomposability of a graph, alternative to treewidth. Branchwidth is polynomially computable on planar graphs by the celebrated ``Ratcatcher''-algorithm of Seymour and Thomas. We investigate an extension of this algorithm to minor-closed graph classes, further than planar graphs as follows: Let $H_{0}$ be a graph embeddedable in the projective plane and $H_{1}$ be a graph embeddedable in the torus. We prove that every $\{H_{0},H_{1}\}$-minor free graph $G$ contains a subgraph $G'$ where the difference between the branchwidth of $G$ and the branchwidth of $G'$ is bounded by some constant, depending only on $H_{0}$ and $H_{1}$. Moreover, the graph $G'$ admits a tree decomposition where all torsos are planar. This decomposition can be used for deriving an EPTAS for branchwidth: For $\{H_{0},H_{1}\}$-minor free graphs, there is a function $f\colon\mathbb{N}\to\mathbb{N}$ and a $(1+\epsilon)$-approximation algorithm for branchwidth, running in time $\mathcal{O}(n^3+f(\frac{1}{\epsilon})\cdot n),$ for every $\epsilon>0$., Comment: arXiv admin note: text overlap with arXiv:2010.12397 by other authors

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}., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 93:1-93:19

\noindent By a seminal result of Valiant, computing the permanent of $(0,1)$-matrices is, in general, $\#\mathsf{P}$-hard. In 1913 P\'olya 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 $K_{3,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 $K_{3,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 $K_{3,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 $\#\mathsf{P}$-hard on bipartite graphs which exclude $K_{5,5}$ as a matching minor. This establishes a first computational lower bound for the problem of counting perfect matchings on matching minor closed classes., Comment: Accepted in SODA 2023

We introduce a new kernelization tool, called rainbow matching technique}, that is appropriate for the design of polynomial kernels for packing problems and their hitting counterparts. Our technique capitalizes on the powerful combinatorial results of [Graf, Harris, Haxell, SODA 2021]. We apply the rainbow matching technique on four (di)graph packing or hitting problems, namely the Triangle-Packing in Tournament problem (TPT), where we ask for a packing of $k$ directed triangles in a tournament, Directed Feedback Vertex Set in Tournament problem (FVST), where we ask for a (hitting) set of at most $k$ vertices which intersects all triangles of a tournament, the Induced 2-Path-Packing (IPP) where we ask for a packing of $k$ induced paths of length two in a graph and Induced 2-Path Hitting Set problem (IPHS), where we ask for a (hitting) set of at most $k$ vertices which intersects all 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\'e, Zehavi. ACM Trans. Algorithms, 2019], where they gave a kernel of $O(k^{3/2})$ vertices for the two first problems and $O(k^{5/3})$ vertices for the two last. In the same paper it was questioned whether these bounds can be (optimally) improved to linear ones. Motivated by this question, we apply the rainbow matching technique and prove that TPT and FVST admit (almost linear) kernels of $k^{1+\frac{O(1)}{\sqrt{\log{k}}}}$ vertices and that IPP and IPHS admit kernels of $O(k)$ vertices., Comment: Accepted to SODA 2023

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