TonyHuynh

Archive of posts with tag 'TonyHuynh'

  • Tony Huynh, Stable sets in graphs with bounded odd cycle packing number

    IBS/KAIST Joint Discrete Math Seminar

    Stable sets in graphs with bounded odd cycle packing number
    Tony Huynh
    Monash University
    2019/11/12 Tue 4:30PM-5:30PM (Room B232, IBS)
    It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs.  The recent bimodular algorithm of Artmann, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles.  The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is a long-standing open problem for all other values of $k$.  We prove that under the additional assumption that the input graph is embedded in a surface of bounded genus, there is a polynomial-time algorithm for each fixed $k$.  Moreover, we obtain polynomial-size extended formulations for the respective stable set polytopes. To this end, we show that 2-sided odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed surface. This result may be of independent interest and extends a theorem of Kawarabayashi and Nakamoto asserting that odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed orientable surface. Eventually, our findings allow us to reduce the original problem to the problem of finding a minimum-cost non-negative integer circulation of a certain homology class, which we prove to be efficiently solvable in our case. This is joint work with Michele Conforti, Samuel Fiorini, Gwenaël Joret, and Stefan Weltge.
    Tags:

  • Tony Huynh, A tight Erdős-Pósa function for planar minors

    IBS/KAIST Joint Discrete Math Seminar

    A tight Erdős-Pósa function for planar minors
    Tony Huynh
    Université libre de Bruxelles
    2018/12/10 5PM-6PM (Room B109, IBS)
    Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function f(k) such that for all k and all graphs G, either G contains k vertex-disjoint subgraphs each containing H as a minor, or there is a subset X of at most f(k) vertices such that G−X has no H-minor. We prove that this remains true with f(k)=ck log k for some constant c depending on H. This bound is best possible, up to the value of c, and improves upon a recent bound of Chekuri and Chuzhoy. The proof is constructive and yields the first polynomial-time O(log ???)-approximation algorithm for packing subgraphs containing an H-minor.</p>

    This is joint work with Wouter Cames van Batenburg, Gwenaël Joret, and Jean-Florent Raymond.

    Tags:

  • Tony Huynh, Space Proof Complexity for Random 3-CNFs
    Space Proof Complexity for Random 3-CNFs
    Tony Huynh
    Dipartimento di Informatica, Sapienza Università di Roma, Rome, Italy
    2015/6/2 Tue 4PM-5PM
    During the last decade, an active line of research in proof complexity has been the space complexity of proofs and how space is related to other complexity measures (like size, length, width, degree). Space is (roughly) how large of an erasable board one would need to show a proof line-by-line.
    Here, we are interested in the space complexity of refuting 3-CNFs (formulas in conjunctive normal form with at most 3 literals per clause). We prove that a random 3-CNF with n variables requires, with high probability, Ω(n2) total space in Resolution. This is best possible up to a constant factor.
    This lower bound is obtained via a variant of Hall’s Lemma which may be of independent interest. Namely, we show that in bipartite graphs G with bipartition (L,R) and left-degree at most 3, L can be covered by certain families of disjoint paths, called VW-matchings, provided that L expands in R by a factor of (2-ε), for ε < 1/23.
    This is joint work with Patrick Bennett, Ilario Bonacina, Nicola Galesi, Mike Molloy, and Paul Wollan.
    Tags:

  • Tony Huynh, Intertwining connectivities for matroids
    Intertwining connectivities for matroids
    Tony Huynh
    Department of Mathematical Sciences, KAIST
    2012/2/29 Wed 4PM-5PM
    An intertwine of two graphs G and H is a graph that has both G and H as a minor and is minor-minimal with this property. In 1979, Lovász and Unger conjectured that for any two graphs G and H, there are only a finite number of intertwines. This now follows from the graph minors project of Robertson and Seymour, although no ‘elementary’ proof is known.
    In this talk, we consider intertwining problems for matroids. Bonin proved that there are matroids M and N that have infinitely many intertwines. However, it is conjectured that if M and N are both representable over a fixed finite field, then there are only finitely many intertwines. We prove a weak version of this conjecture where we intertwine ‘connectivities’ instead of minors. No knowledge of matroid theory will be assumed.
    This is joint work with Bert Gerards (CWI, Amsterdam) and Stefan van Zwam (Princeton University).
    Tags:

Monthly Archives