Search

A graph is O k -free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite graphs as subgraphs) O k -free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is optimal, as there is an infinite family of O 2 -free graphs without K 2 , 3 as a subgraph and whose treewidth is (at least) logarithmic. Using our result, we show that Maximum Independent Set and 3-Coloring in O k -free graphs can be solved in quasi-polynomial time. Other consequences include that most of the central NP-complete problems (such as Maximum Independent Set , Minimum Vertex Cover , Minimum Dominating Set , Minimum Coloring) can be solved in polynomial time in sparse O k -free graphs, and that deciding the O k -freeness of sparse graphs is polynomial time solvable. [ABSTRACT FROM AUTHOR]

Let G be an intersection graph of n geometric objects in the plane. We show that a maximum matching in G can be found in O (ρ 3 ω / 2 n ω / 2) time with high probability, where ρ is the density of the geometric objects and ω > 2 is a constant such that n × n matrices can be multiplied in O (n ω) time. The same result holds for any subgraph of G, as long as a geometric representation is at hand. For this, we combine algebraic methods, namely computing the rank of a matrix via Gaussian elimination, with the fact that geometric intersection graphs have small separators. We also show that in many interesting cases, the maximum matching problem in a general geometric intersection graph can be reduced to the case of bounded density. In particular, a maximum matching in the intersection graph of any family of translates of a convex object in the plane can be found in O (n ω / 2) time with high probability, and a maximum matching in the intersection graph of a family of planar disks with radii in [ 1 , Ψ ] can be found in O (Ψ 6 log 11 n + Ψ 12 ω n ω / 2) time with high probability. [ABSTRACT FROM AUTHOR]

A perfect matching cut is a perfect matching that is also a cutset, or equivalently, a perfect matching containing an even number of edges on every cycle. The corresponding algorithmic problem, Perfect Matching Cut , is known to be NP-complete in subcubic bipartite graphs [Le & Telle, TCS '22], but its complexity was open in planar graphs and cubic graphs. We settle both questions simultaneously by showing that Perfect Matching Cut is NP-complete in 3-connected cubic bipartite planar graphs or Barnette graphs. Prior to our work, among problems whose input is solely an undirected graph, only Distance-2 4-Coloring was known to be NP-complete in Barnette graphs. Notably, Hamiltonian Cycle would only join this private club if Barnette's conjecture were refuted. [ABSTRACT FROM AUTHOR]

We give essentially tight bounds for, ν (d , k) , the maximum number of distinct neighbourhoods on a set X of k vertices in a graph with twin-width at most d. Using the celebrated Marcus–Tardos theorem, two independent works (Bonnet et al., 2022; Przybyszewski, 2022) have shown the upper bound ν (d , k) ⩽ exp (exp (O (d))) k , with a double-exponential dependence in the twin-width. The work of Gajarsky et al. (2022), using the framework of local types, implies the existence of a single-exponential bound (without explicitly stating such a bound). We give such an explicit bound, and prove that it is essentially tight. Indeed, we give a short self-contained proof that for every d and k ν (d , k) ⩽ (d + 2) 2 d + 1 k = 2 d + log d + Θ (1) k , and build a bipartite graph implying ν (d , k) ⩾ 2 d + log d + Θ (1) k , in the regime when k is large enough compared to d. [ABSTRACT FROM AUTHOR]

We study the polynomial time approximation of the NP -hard max k - vertex cover problem in bipartite graphs and propose purely combinatorial approximation algorithms . The main result of the paper is a simple combinatorial algorithm and a computer-assisted analysis of its approximation guarantee giving strong evidence that the worst approximation ratio achieved is bounded below by 0.821. We also study two simpler strategies with provable approximation ratios of 2 3 and 34 47 ≈ 0 . 72 respectively that already beat the only such known algorithm, namely the greedy approach which guarantees ratio ( 1 − 1 e ) ≈ 0 . 632 . Our principal motivation is to bring a satisfactory answer in the following question: to what extent combinatorial methods for max k - vertex cover compete with linear programming ones? [ABSTRACT FROM AUTHOR]