More Like this

1. Reconfiguration of Connected Graph Partitions via Recombination

   https://doi.org/10.1007/978-3-030-75242-2_4  

   Akitaya, Hugo A.; Korman, Matias; Korten, Oliver; Souvaine, Diane L.; Toth, Csaba D. (May 2021, Algorithms and Complexity (CIAC 2021))

   null (Ed.)

   Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph G. A partition of V(G) is connected if every part induces a connected subgraph. In many applications, it is desirable to obtain parts of roughly the same size, possibly with some slack s. A Balanced Connected k-Partition with slack s, denoted (k, s)-BCP, is a partition of V(G) into k nonempty subsets, of sizes n1,…,nk with |ni−n/k|≤s , each of which induces a connected subgraph (when s=0 , the k parts are perfectly balanced, and we call it k-BCP for short). A recombination is an operation that takes a (k, s)-BCP of a graph G and produces another by merging two adjacent subgraphs and repartitioning them. Given two k-BCPs, A and B, of G and a slack s≥0 , we wish to determine whether there exists a sequence of recombinations that transform A into B via (k, s)-BCPs. We obtain four results related to this problem: (1) When s is unbounded, the transformation is always possible using at most 6(k−1) recombinations. (2) If G is Hamiltonian, the transformation is possible using O(kn) recombinations for any s≥n/k , and (3) we provide negative instances for s≤n/(3k) . (4) We show that the problem is PSPACE-complete when k∈O(nε) and s∈O(n1−ε) , for any constant 0<ε≤1 , even for restricted settings such as when G is an edge-maximal planar graph or when k≥3 and G is planar. 

   more » « less
2. New upper bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers

   https://doi.org/10.1017/S0963548322000293  

   Cameron, Alex; Heath, Emily (March 2023, Combinatorics, Probability and Computing)

   Abstract A$$(p,q)$$-colouring of a graph$$G$$is an edge-colouring of$$G$$which assigns at least$$q$$colours to each$$p$$-clique. The problem of determining the minimum number of colours,$$f(n,p,q)$$, needed to give a$$(p,q)$$-colouring of the complete graph$$K_n$$is a natural generalization of the well-known problem of identifying the diagonal Ramsey numbers$$r_k(p)$$. The best-known general upper bound on$$f(n,p,q)$$was given by Erdős and Gyárfás in 1997 using a probabilistic argument. Since then, improved bounds in the cases where$$p=q$$have been obtained only for$$p\in \{4,5\}$$, each of which was proved by giving a deterministic construction which combined a$$(p,p-1)$$-colouring using few colours with an algebraic colouring. In this paper, we provide a framework for proving new upper bounds on$$f(n,p,p)$$in the style of these earlier constructions. We characterize all colourings of$$p$$-cliques with$$p-1$$colours which can appear in our modified version of the$$(p,p-1)$$-colouring of Conlon, Fox, Lee, and Sudakov. This allows us to greatly reduce the amount of case-checking required in identifying$$(p,p)$$-colourings, which would otherwise make this problem intractable for large values of$$p$$. In addition, we generalize our algebraic colouring from the$$p=5$$setting and use this to give improved upper bounds on$$f(n,6,6)$$and$$f(n,8,8)$$. 

   more » « less
3. Clique minors in graphs with a forbidden subgraph

   https://doi.org/10.1002/rsa.21038  

   Bucić, Matija; Fox, Jacob; Sudakov, Benny (August 2021, Random Structures & Algorithms)

   Abstract The classical Hadwiger conjecture dating back to 1940s states that any graph of chromatic number at leastrhas the clique of orderras a minor. Hadwiger's conjecture is an example of a well‐studied class of problems asking how large a clique minor one can guarantee in a graph with certain restrictions. One problem of this type asks what is the largest size of a clique minor in a graph onnvertices of independence numberat mostr. If true Hadwiger's conjecture would imply the existence of a clique minor of order. Results of Kühn and Osthus and Krivelevich and Sudakov imply that if one assumes in addition thatGisH‐free for some bipartite graphHthen one can find a polynomially larger clique minor. This has recently been extended to triangle‐free graphs by Dvořák and Yepremyan, answering a question of Norin. We complete the picture and show that the same is true for arbitrary graphH, answering a question of Dvořák and Yepremyan. In particular, we show that any‐free graph has a clique minor of order, for some constantdepending only ons. The exponent in this result is tight up to a constant factor in front of theterm. 

   more » « less
4. Approximation Algorithm for Norm Multiway Cut

   https://doi.org/10.4230/LIPIcs.ESA.2023.32  

   Carlson, Charlie; Jafarov, Jafar; Makarychev, Konstantin; Makarychev, Yury; Shan, Liren (August 2023, Proceedings of the European Symposium on Algorithms)

   Gørtz, Inge Li; Farach-Colton, Martin; Puglisi, Simon J; Herman, Grzegorz (Ed.)

   We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph G into k parts so as to separate k given terminals. Recently, Chandrasekaran and Wang (ESA 2021) introduced l_p-norm Multiway Cut, a generalization of the problem, in which the goal is to minimize the l_p norm of the edge boundaries of k parts. We provide an O(log^{1/2} n log^{1/2 + 1/p} k) approximation algorithm for this problem, improving upon the approximation guarantee of O(log^{3/2} n log^{1/2} k) due to Chandrasekaran and Wang. We also introduce and study Norm Multiway Cut, a further generalization of Multiway Cut. We assume that we are given access to an oracle, which answers certain queries about the norm. We present an O(log^{1/2} n log^{7/2} k) approximation algorithm with a weaker oracle and an O(log^{1/2} n log^{5/2} k) approximation algorithm with a stronger oracle. Additionally, we show that without any oracle access, there is no n^{1/4-ε} approximation algorithm for every ε > 0 assuming the Hypergraph Dense-vs-Random Conjecture. 

   more » « less
5. On Approximating Degree-Bounded Network Design Problems

   https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.39  

   Xiangyu Guo, Guy Kortsarz (October 2020, Leibniz international proceedings in informatics)

   null (Ed.)

   Directed Steiner Tree (DST) is a central problem in combinatorial optimization and theoretical computer science: Given a directed graph G = (V, E) with edge costs c ∈ ℝ_{≥ 0}^E, a root r ∈ V and k terminals K ⊆ V, we need to output a minimum-cost arborescence in G that contains an rrightarrow t path for every t ∈ K. Recently, Grandoni, Laekhanukit and Li, and independently Ghuge and Nagarajan, gave quasi-polynomial time O(log²k/log log k)-approximation algorithms for the problem, which are tight under popular complexity assumptions. In this paper, we consider the more general Degree-Bounded Directed Steiner Tree (DB-DST) problem, where we are additionally given a degree bound d_v on each vertex v ∈ V, and we require that every vertex v in the output tree has at most d_v children. We give a quasi-polynomial time (O(log n log k), O(log² n))-bicriteria approximation: The algorithm produces a solution with cost at most O(log nlog k) times the cost of the optimum solution that violates the degree constraints by at most a factor of O(log²n). This is the first non-trivial result for the problem. While our cost-guarantee is nearly optimal, the degree violation factor of O(log²n) is an O(log n)-factor away from the approximation lower bound of Ω(log n) from the Set Cover hardness. The hardness result holds even on the special case of the Degree-Bounded Group Steiner Tree problem on trees (DB-GST-T). With the hope of closing the gap, we study the question of whether the degree violation factor can be made tight for this special case. We answer the question in the affirmative by giving an (O(log nlog k), O(log n))-bicriteria approximation algorithm for DB-GST-T. 

   more » « less