Ciclos Hamiltonianos em Produtos Cartesianos de Grafos
Palestrante: Jorge Pucohuaranga (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 18/09 às 14:00.
Resumo:
Dado um grafo \(G\), o problema do ciclo hamiltoniano consiste em determinar se existe um ciclo que passa por todos os vértices de \(G\) exatamente uma vez. Devido à dificuldade inerente a um problema NP-Completo, uma tendência recente tem sido procurar por ciclos longos, buscando determinar o ciclo com o maior número de vértices possível. Outra tendência consiste na busca por estruturas relacionadas. Neste aspecto, ser um grafo prisma-hamiltoniano tem se mostrado ser uma relaxação interessante de ser hamiltoniano. O prisma de um grafo \(G\) consiste em duas cópias de \(G\) com uma aresta unindo cada par de vértices correspondentes. Se o prisma de \(G\) contém um ciclo hamiltoniano então \(G\) é prisma-hamiltoniano. Estudamos uma conjectura que afirma que todo grafo 4-regular 4-conexo é prisma-hamiltoniano. Provamos essa conjectura para grafos livres de garras. De fato, para uma subclasse dos grafos \(4\)-regulares \(4\)-conexos livres de garras, provamos um resultado mais forte: sua hamiltonicidade; corroborando assim com outra conjectura de 1993 que afirma que grafos \(4\)-regulares \(4\)-conexos livres de garras são hamiltonianos. Dado um grafo \(G\), seja \(G^1=G* K_2\) e \(G^q=G^{q-1}* K_2\), para \(q>1\). Mostramos que, para todo grafo conexo \(G\), temos que \(G^q\) é hamiltoniano para todo \(q\geq \lceil \log_2 \Delta(G) \rceil\), onde \(\Delta(G)\) é o grau máximo de \(G\).
Trading off Worst and Expected Cost in Decision Tree Problems
Palestrante: Eduardo Laber (PUC-Rio)
Onde e quando: Auditório NUMEC, sexta-feira 11/09 às 14:00.
Resumo:
We characterize the best possible trade-off achievable when optimizing the construction of a decision tree with respect to both the worst and the expected cost. It is known that a decision tree achieving the minimum possible worst case cost can behave very poorly in expectation (even exponentially worse than the optimal), and the vice versa is also true. Led by applications where deciding for the right optimization criterion might not be easy, recently, several authors have focused on the bicriteria optimization of decision trees.
An unanswered fundamental question is about the best possible trade-off achievable. Here we are able to sharply define the limits for such a task. More precisely, for any instance \(I\) and for every \(\rho>0\) we show that there is a decision tree \(D\) with worst testing cost at most \((1 + \rho)OPT_W(I)+1\) and expected testing cost at most \(\frac{1}{1 – e^{-\rho}} OPT_E(I)\), where \(OPT_W(I)\) and \(OPT_E(I)\) are, respectively, the minimum worst testing cost and the minimum expected testing cost of a decision tree for the instance \(I\). We also show that this is the best possible trade-off in the sense that there are infinitely many instances for which we cannot obtain a decision tree with both worst testing cost smaller than \((1 + \rho)OPT_W(I)\) and expected testing cost smaller than \(\frac{1}{1 – e^{-\rho}} OPT_E(I)\).
Polynomial Optimization with Symmetries
Palestrante: Fabrício Caluza Machado (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 28/08 às 14:00.
Resumo:
It is well known that the problem of global minimization for multivariate polynomials is an NP-hard problem. However, there are techniques to provide certifiable lower bounds for it and when the minimization is taken over certain domains, results like the Positivstellensatz of Putinar plays an important role. On this seminar, I will talk about this and also how big problems can be simplified under the presence of symmetries.
An Approximation algorithm for the Minimum Max-Stretch spanning Tree Problem on Unweighted Graphs
Palestrante: Hugo Braga (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 4/09 às 14:00.
Resumo:
Given a graph \(G\), where \(n = |V(G)|\), and a spanning tree \(T\) of \(G\), we say that \(T\) is a tree \(t\)-spanner of \(G\) if the distance between every pair of vertices in \(T\) is at most \(t\) times their distance in \(G\). The problem of finding a tree \(t\)-spanner minimizing \(t\) is referred as the Minimum Max-Stretch spanning Tree (MMST) problem. This problem is known to be NP-hard. On this seminar, I will talk about spanners and present an \(O(log n)\)-approximation algorithm for the MMST problem on unweighted graphs proposed by Emek and Peleg in 2008.
Spanning trees with nonseparating paths
Palestrante: César Israel Hernández (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 26/06 às 14:00.
Resumo:
We consider questions related to the existence of spanning trees in connected graphs with the property that, after the removal of any path in the tree, the graph remains connected. We show that, for planar graphs, the existence of trees with this property is closely related to the Hamiltonicity of the graph. We also deal with spanning trees satisfying this property restricted to paths arising from fundamental cycles. We are also interested in the existence of a fundamental basis consisting of nonseparating cycles.
(Joint work with Cristina G. Fernandes, Orlando Lee, and José C. de Pina.)
The Capacitated Fault-Tolerant \(k\)-Center
Palestrante: Lehilton Pedrosa (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 12/06 às 14:00.
Resumo:
In the classical \(k\)-center problem, we are given an integer \(k\) and a metric space \(V\), and want to choose \(k\) center in \(V\), and an assignment of the elements in \(V\) to these centers that minimizes the maximum distance between an element of \(V\) and its assigned center. While this basic problem is well understood, generalizations have been considered: in the so called capacitated \(\alpha\)-fault-tolerant \(k\)-center, each center has a limited capacity on the number of assigned elements, and one wants to obtain a set of \(k\) centers, so that, even if \(\alpha\) of these centers fail, there is an assignment from \(V\) to the non-faulty centers respecting their capacities. We will show how to use a linear programming formulation to obtain a 10-approximation for this problem in the general case when capacities are non-uniform. Our algorithm may be specialized to the case that capacities are either 0 or a constant \(L\), obtaining a factor 6. This improves the previous 9-approximation for uniform capacities, that was the only approximation known before.
Size Ramsey Numbers of Bounded Degree Subdivisions
Palestrante: Troy John Retter (Emory University)
Onde e quando: Auditório NUMEC, sexta-feira 29/05 às 15:30.
Resumo:
For a graph \(S\), the \(h\)-subdivision \(S^{(h)}\) is obtained by replacing each edge of \(S\) with a path on \(h\) internal vertices. For fixed \(D\) and \(h\), we show that for any graph \(S\) on \(n\) vertices with maximum degree at most \(D\), there exists a graph \(G\) with \(n^{1+1/(h+1)+o(1)}\) edges having the following property: every red and blue coloring of the edge of \(G\) yields a monochromatic copy of \(S^{(h)}\).
This establishes bounds on the size Ramsey number of `short’ subdivisions. It complements work of Pak regarding `long’ subdivisions, and is related to the more general open problem of determining the size Ramsey number for graphs with bounded degree.
This is joint work with Y. Kohayakawa and V. Rödl.
Minimum \(k\)-Section in bounded degree trees
Palestrante: Tina Schmidt (Hamburg University of Technology)
Onde e quando: Auditório NUMEC, sexta-feira 29/05 às 14:00.
Resumo:
Minimum \(k\)-Section denotes the NP-hard problem to partition the vertex set of a graph into \(k\) sets of size as equal as possible while minimizing the cut width, which is the number of edges between these sets. When \(k\) is an input parameter and \(n\) denotes the number of vertices, it is NP-hard to approximate the width of a minimum \(k\)-section within a factor of \(n^c\) for any \(c <1\), even when restricted to trees with constant diameter. Here, we show that every tree \(T\) allows a \(k\)-section of width at most \( (k-1) (2 + 16n / \mathrm{diam}(T) ) \Delta(T) \). This implies a polynomial time constant factor approximation for the Minimum \(k\)-Section Problem when restricted to trees with linear diameter and constant maximum degree. This is joint work with Cristina G. Fernandes and Anusch Taraz. Applications of flag algebras to tournaments II: Quasi-carousel tournaments
Palestrante: Leonardo Nagami Coregliano (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 22/05 às 14:00.
Resumo:
In 1989, F. Chung, R. Graham and R. Wilson proved the equivalence of the so called “quasi-random graph properties”, which are several a priori very different properties of the sequence of Erdős–Rényi random graphs that may be used to say that another sequence “looks like” a sample of it.
The quasi-randomness theory has since then been expanded to several other theories, one of them, the theory of quasi-random tournaments, was initiated by Chung and Graham in 1991.
Continuing the previous talk, we will show another application of flag algebras to tournaments by proving the equivalence of a set of properties analogous to the quasi-random properties characterizing sequences we called “quasi-carousel”.
Applications of flag algebras to tournaments I: Minimum density of transitive tournaments
Palestrante: Leonardo Nagami Coregliano (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 15/05 às 14:00.
Resumo:
In 2007, Alexander A. Razborov developed the theory of flag algebras to compute the minimum density of triangles in a graph as a function of its edge density. The proof techniques in flag algebras can be subdivided into three types: the semidefinite method, the inductive method and the differential method.
The inductive method allows us to translate classical combinatorial arguments to the limit objects provided by flag algebra calculus yielding short and elegant proofs.
Using this method we proved that the density of transitive tournaments on at least 4 vertices is asymptotically minimized only by the quasi-random tournaments.
The aim of this talk is to show the intuition behind this instance of the inductive method. We will do so by presenting the same proof twice: the first time using flag algebra arguments and the second time using only classical arguments.
This is a joint work with Alexander A. Razborov.
Anticadeias máximas em conjuntos aleatórios
Palestrante: Maurício Collares (IMPA)
Onde e quando: Auditório NUMEC, sexta-feira 08/05 às 15:30.
Resumo:
Um dos primeiros e mais famosos resultados sobre sistemas de conjuntos é o Teorema de Sperner, provado em 1928: A maior anticadeia (família que não contém dois conjuntos encaixados) contida em \(P(n)\), o conjunto das partes de \({1, \ldots, n}\), tem cardinalidade \(n\choose n/2\).
Denotaremos por \(P(n, p)\) o subconjunto aleatório de \(P(n)\) em que cada elemento é incluído (independentemente dos outros) com probabilidade \(p\). Em 1954, Rényi iniciou o estudo de subconjuntos aleatórios de \(P(n)\), provando um limiar para a propriedade “\(P(n, p)\) é uma anticadeia”. Mais precisamente, ele mostrou que existe uma função \(f(n)\) tal que a propriedade acima é verdadeira (resp. falsa) com alta probabilidade se \(p(n)/f(n)\) vai a zero (resp. infinito). Tal resultado fundou uma interessante linha de pesquisa da combinatória moderna.
Em 2000, Osthus estudou uma versão aleatória do teorema de Sperner, investigando a propriedade “A maior anticadeia de \(P(n, p)\) tem cardinalidade \((1 + o(1)) p {n\choose n/2}\)”. Ele mostrou que tal propriedade é falsa com alta probabilidade se pn é limitado, e é verdadeira com alta probabilidade se \(pn/\log n\) vai a infinito. Tal resultado quase mostra a existência de um limiar, e assim Osthus caracterizou como “muito interessante” a questão de saber se o termo logarítmico pode ser removido.
No nosso trabalho, em conjunto com Rob Morris, respondemos afirmativamente tal pergunta, mostrando que a propriedade em questão é verdadeira com alta probabilidade se pn vai a infinito (e portanto determinando um limiar para a mesma). Também mostramos um resultado análogo para famílias que evitam \(k\) conjuntos encaixados.
Perfect Matchings in Dense Uniform Hypergraphs
Palestrante: Jie Han (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 08/05 às 14:00.
Resumo:
In graph/hypergraph theory, perfect matchings are fundamental objects of study. Unlike the graph case, perfect matchings in hypergraphs have not been well understood yet. It is quite natural and desirable to extend the classical theory on perfect matchings from graphs to hypergraphs, as many important problems can be phrased in this framework, such as Ryser’s conjecture on transversals in Latin squares and the Existence Conjecture for block designs. I will focus on Dirac-type conditions (minimum degree conditions) in uniform hypergraphs and discuss some recent progresses. In particular, we determine the minimum codegree threshold for the existence of a near perfect matching in hypergraphs, which confirms a conjecture of Rödl, Ruciński and Szemerédi, and we show that there is a polynomial-time algorithm that can determine whether a \(k\)-uniform hypergraph with minimum codegree \(n/k\) has a perfect matching, which solves a problem of Karpiński, Ruciński and Szymańska completely.
Quadratizations of Pseudo-Boolean Functions
Palestrante: Aritanan Borges Garcia Gruber (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 24/04 às 14:00.
Resumo:
The problem of minimizing pseudo-Boolean functions (i.e., real-valued mapping over the set of binary vectors, specified as multilinear polynomials) encompasses numerous optimization models, including the well-known MAX-SAT and MAX-CUT problems, and has applications in areas ranging from physics through chip design to computer vision.
When the application leads to the minimization of a quadratic pseudo-Boolean function, one of the most frequently used technique is based on roof-duality (Hamer, Hansen, Simeone, 1984), and it aims at finding in polynomial time a simpler form of the given quadratic minimization problem, by fixing some of the variables at their provably optimum value (persistency) and decomposing the residual problem into variable disjoint smaller subproblems (Boros and Hammer, 1989). The method in fact was found very effective in some computer vision problems, where frequently it can fix up to 80-90% of the variables at their provably optimum value (Boros, Hammer, Sun and Tavares, 2008).
In the past decade, many applications of pseudo-Boolean optimization, specially those stemming from the computer vision community, have a higher degree multilinear polynomial as objective function. For such problems there are much fewer effective techniques available. In particular, there is no analogue to the persistencies provided by roof-duality for the quadratic case. This increased interest led to the study of methods to reduce a higher degree minimization problem to a quadratic one. There are many techniques to achieve this goal, most of them based on local transformations. It is however not clear how large the resulting quadratic problems can be.
We follow a global approach, considering all possible quadratizations of a given higher degree pseudo-Boolean function, and provide sharp lower and upper bounds on the number of extra variables needed to quadratize those. In fact we consider several different types of quadratizatons, and provide sharp bounds for each. These results give rise to new quadratization algorithms, as well. We also report on some computational results which we got via a collaboration with Alex Fix and Ramin Zabih (Cornell University, NY, USA).
(Joint work with M. Anthony, E. Boros, and Y. Crama.)
On the proper orientation number of bipartite graphs
Palestrante: Phablo Moura (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 10/04 às 14:00.
Resumo:
An orientation of a graph \(G\) is a digraph \(D\) obtained from \(G\) by replacing each edge by exactly one of the two possible arcs with the same endvertices. For each \(v \in V(G)\), the indegree of \(v\) in \(D\), denoted by \(d^-_D(v)\), is the number of arcs with head \(v\) in \(D\). An orientation \(D\) of \(G\) is proper if \(d^-_D(u)\neq d^-_D(v)\), for all \(uv\in E(G)\). The proper orientation number of a graph \(G\) is the minimum of the maximum indegree over all its proper orientations. In this talk, we will show bounds on the proper orientation number of bipartite graphs and hardness results.
Joint work with J. Araujo, N. Cohen, S. de Rezende, and F. Havet.
Aplicação do método semidefinido de álgebra de flags para torneios
Palestrante: Roberto Parente (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 27/03 às 14:00.
Resumo:
Em 2010, A. Razborov, utilizando álgebra de flags, apresentou o método semidefinido que permite obtermos rapidamente limitantes para problemas de combinatória extremal. No seminário apresentaremos o método semidefinido para torneios e uma técnica proposta por R. Baber de como obtermos limitantes para problemas de combinatória extremal utilizandos os resultados computacionais.
An Introduction to the Technique of Hypergraph Containers
Palestrante: Antônio Josefran O. Bastos (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 20/03 às 14:00.
Resumo:
In 2013, Saxton and Thomason, and Balogh, Morris and Samotij independently developed a technique known as hypergraphs containers. This technique has been used to obtain various results on embedding problems. For example, in 2013, Morris and Saxton used hypergraphs containers to prove that the number of \(C_ {2l \ell}\)-free graph, where \(\ell\) is a positive integer, is at most \(2^{O(n^{1+1/\ell})}\). In this seminar, I will give an introduction to this new tool.
Limitantes para o número de contato via programação semidefinida
Palestrante: Fabrício Caluza Machado (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 13/03 às 14:00
Resumo:
O problema do número de contato trata do maior número de esferas que podem tocar uma esfera central em dimensão \(n\) (todas de mesmo raio). A obtenção de limitantes superiores para este número é um problema de otimização combinatória rico em simetrias e exige o estudo de técnicas que as aproveitem.
Neste seminário, veremos o clássico limitante de Delsarte (Delsarte, Goethals e Seidel, 1973) interpretado em termos do número teta de Lovász (Bachoc, Nebe, Oliveira e Vallentin, 2008) e o mais moderno limitante via programação semidefinida, apresentado por Bachoc e Vallentin (2008).
Esparsificação de grafos e de matrizes positivas semidefinidas
Palestrante: Marcel K. de Carli Silva (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 06/03 às 14:00.
Resumo:
Um esparsificador de cortes de um grafo \(G\) com pesos nas arestas é um subgrafo gerador esparso \(H\) de \(G\) com novos pesos nas arestas tal que, para cada corte, os pesos do corte em \(H\) e em \(G\) estão dentro de um fator multiplicativo de \((1\pm\varepsilon)\) um do outro. Benczúr e Karger provaram que todo grafo com \(m\) arestas e \(n\) vértices possui um esparsificador de cortes com \(O(n\log(n)/\varepsilon^2)\) arestas.
Um esparsificador espectral de um grafo é definido de forma semelhante, porém preservando a forma quadrática determinada por seu laplaciano. Tais esparsificadores também são esparsificadores de cortes e têm outras aplicações poderosas em resolvedores de sistemas lineares, em grande parte devido ao trabalho seminal de Spielman e Teng.
Neste seminário, vamos ver algumas aplicações de tais esparsificadores e (esboços de) algoritmos que os constroem, bem como um resultado mais geral para somas de matrizes positivas semidefinidas.
(Trabalho em conjunto com Cristiane M. Sato e Nicholas J.A. Harvey.)
Efficient Construction of Minimal Spline Bases
Palestrante: Jorge Stolfi (UNICAMP)
Onde e quando: Auditório NUMEC, sexta-feira 23/01 às 14:00.
Resumo:
A spline is a function defined by parts. Namely, the domain of interest is divided into a /mesh/ with a finite number {n} of /cells/, and within each cell the function is defined by a separate mathematical formula, such as a polynomial of bounded degree. Splines are widely used in numerical computing, since they can be evaluated very quickly, and can approximate complicated functions to arbitrary accuracy, even when the accuracy requirement is not uniform over the domain.
In many applications, the splines are required to satisfy some continuity or other constraints between adjacent parts. It is often the case that the space {S} of all valid (constrained) splines is much smaller than the space {U} of all unconstrained splines with the same mesh and type. It is therefore advisable to precompute a /basis/ for the space {S}; that is, a minimal list {B[1..m]} of splines from {S} that can generate all the valid splines by linear combination. Once the basis {B} is chosen, each valid spline {s} in {S} can be represented by the list of its {m} coefficients {a[1..m]} relative to {B}.
To evaluate a spline {s}, given in that representation, at some domain point {x}, one should first locate the cell {C} of the mesh that contains {x}, then compute the polynomial {P = SUM{k : a[k]*(B[k]|C)}}, and then evaluate P at {x}. Note that one needs to include in the sum only those elements of {B} that are not identically zero in the cell {C}. Therefore, it is desirable to choose the elements of {B} so that they have /compact support/, that is, non-zero only in a small number of cells. Indeed, it is desirable to minimize the /weight/ of {B}, defined as the number of cells where each element is not zero, summed over all elements.
Traditionally, the search for compact bases is done by hand, case by case, by constructions that are specific to each type of meshand degree. For many cases of practical interest, the existence of a compact basis is not known, or it is not known whether a known compact basis is optimal.
Surprisingly, there is an algorithm that will find a minimal-weight basis for any constrained spline space {S}, that runs in polynomial time when a compact basis exists. The algorithm relies on the fact that the constrained splines define a matroid, and therefore the minimum-weight basis can be found by the classical greedy algorithm of Edmonds.
The algorithm requires enumerating every subset {Z} of cells that is connected in the dual graph of the mesh, in order of increasing cardinality, and enumerating the elements of the basis whose support is {Z} and are not combinations of previously found elements. Although the number of subsets {Z} of a fixed cardinality {z} is proportional to {n^z}, the number of /connected/ subsets is only {O(n)}, with a constant factor that depends only on {z} and the maximum degree of the dual graph. The algorithm is fast enough to be useful in practical applications.
These results are part of the PhD thesis project of Ana Paula Malheiro.