Em um polígono $P$ dois vértices se enxergam se o segmento que os une é não exterior a $P$. O grafo de visibilidade de um polígono $P$ contem um arco se e somente se dois dois vértices de $P$ se enxergam.

Um polígono é um leque convexo se existe um vértice convexo que enxerga todo o polígono. Um polígono é unimonótono se sua fronteira pode ser dividida em uma cadeia monótona com relação a uma reta e uma aresta.

Dado um grafo arbitrário $G$, o problema de reconhecimento procura decidir se $G$ é um grafo de visibilidade. O problema de reconstrução procura um polígono cujo grafo de visibilidade é isomorfo a um grafo de visibilidade dado como entrada.

Apesar de ambos os polígonos apresentados aparentarem não ser relacionados, neste seminário mostraremos que os problemas de reconhecimento e reconstrução de ambas as classes são equivalentes através de reduções.

Cartogramas são ferramentas para visualização de dados sobre um conjunto de países ou estados em um mapa. Há diferentes tipos de cartogramas e, para alguns deles, existem algoritmos para automatizar sua construção. Neste trabalho, estudamos cartogramas em mosaicos, i.e., cartogramas que utilizam conjuntos de ladrilhos para representar regiões. Cartogramas em mosaicos permitem uma comparação precisa de dados associados a diferentes regiões e, freqüentemente, possibilitam também uma representação (esquematizada) dos contornos do mapa original. Nós propomos o primeiro procedimento totalmente automatizado para construir tais cartogramas. O método proposto foi validado experimentalmente e os resultados mostram que os cartogramas gerados apresentam erros cartográficos relativamente pequenos se comparados a outros métodos.

A palestra discorrerá sobre ataques de recuperação de chave privada em uma família de criptossistemas homomórficos. A criptografia homomórfica é interessante porque permite a manipulação algébrica de textos cifrados. Isto é, podemos somar e multiplicar estes textos cifrados, de modo que o resultado corresponda as mesmas operações aplicadas sobre os respectivos textos claros. Este tipo de primitiva permite a construção de aplicações muito interesssantes, porém é necessário tomar especial cuidado com o modelo de segurança que é adotado. A construção de criptografia homomórfica é impossível no modelo de segurança conhecido como CCA2. Já o modelo de segurança CCA1, menos restritivo, pode teoricamente ser atingido, porém, a maior parte dos esquemas propostos na literatura não são “CCA1-seguros”. Nesta palestra serão apresentados ataques que mostram que uma família de criptossistemas homomórficos não podem ser considerados seguros de acordo com o modelo CCA1, comprovando que a construção deste tipo de criptografia, neste modelo de segurança, não é uma tarefa trivial.

Dado um digrafo $D$, um $k$-sistema de caminhos é uma família de no máximo $k$ caminhos disjuntos nos vértices. O peso de um $k$-sistema de caminhos $\mathcal{P}^k = {P_1, P_2, \ldots, P_m}$ é $||\mathcal{P}^k|| = \sum_{i = 1}^{m} |P_i|$ e dizemos que $\mathcal{P}^k$ é ótimo se $||\mathcal{P}^k||$ é o maior possível.
Uma coloração $\mathcal{C} = {C_1, C_2, \ldots, C_m}$ e um $k$-sistema de caminhos $\mathcal{P}^k$ são ortogonais se cada classe de cor $C_i \in \mathcal{C}$ possui interseção com $\min{|C_i|, k}$ caminhos distintos de $\mathcal{P}^k$. A Conjectura de Aharoni-Hartman-Hoffman diz que todo $k$-sistema de caminhos ótimo possui uma coloração ortogonal a ele [1]. Neste seminário, veremos os resultados parciais sobre a conjectura apresentados em [2].

Referência(s):
[1] Aharoni, Ron, Hartman, Irith Ben-Arroyo & Hoffman (1985). Path partitions and packs of acyclic digraphs. Pacific Journal of Mathematics, 2, 249-259.
[2] Hartman, Irith Ben-Arroyo & Saleh, Fathi and (1994). On greene’s theorem for digraphs. Journal of Graph Theory, 18, 169-175.

Originado a partir do jogo Lights Out [1], um jogo $(G,c)$ de ELLO é caracterizado por uma 2-coloração inicial onde $c:V(G) \rightarrow {\mbox{verde}, \mbox{vermelho}}$ e o movimento permitido consiste em escolher um vértice verde $u$ do grafo atual, trocar a cor de todos os vértices adjacentes a $u$ e remover o vértice $u$ do grafo atual. O processo é repetido até que não se possa realizar mais movimentos e o jogo é ganho se todos os vértices são removidos.
Este seminário abordará os resultados obtidos para caracterizar jogos ganháveis de ELLO em determinadas classes de grafos, mostrando condições necessárias e suficientes para a ganhabilidade do jogo independentemente de sua coloração inicial. Além disso, apresentará algoritmos eficientes para determinar se um jogo ELLO é ganhável [2].

Referência(s):
[1] D. Hooper. Graph domination and the lights out puzzle. Washington State University, 2001.
[2] D. Craft, Z. Miller, and D. Pritikin. A solitaire game played on 2-colored graphs. Elsevier Discrete Mathematics, volume 309, pages 188–201, 2009.

Dado um grafo $G$ com peso nas arestas e um inteiro $L$, o problema da árvore geradora mínima com pelo menos $L$ folhas é encontrar uma árvore geradora de peso mínimo que tenha pelo menos $L$ folhas. Sabe-se que o problema é NP-difícil. Neste seminário, veremos heurísticas, soluções exatas e alguns resultados para instâncias conhecidas do problema.

In phylogenetic analysis one is given a matrix of pairwise distances between a set $S$ of $N$ items, and looks for a tree $T$ with edge costs, with minimum total edge length, whose vertex set $V(T)$ includes $S$, such that the path lengths on $T$ between the vertices in $S$ are as close as possible to the given distances.
In this talk we consider the similar problem where the desired output is not a tree but an arbitrary graph $G$, again with minimum total edge length, and the path lengths have to be equal to the given distances. We consider in particular the variant where the distance matrix is asymmetric and the graph $G$ is a directed graph.

The all pairs suffix-prefix matching problem is well known in stringology. This problem has been solved optimally using powerful data structures (e.g., suffix trees and enhanced suffix arrays). In this work, we present another optimal algorithm which outperforms other alternatives in both time and space. The new algorithm is also based on an enhanced suffix array, as in the best known practical solution of Ohlebusch and Gog in 2010, but scans this structure in a different way. Our algorithm solves the problem locally for each string, scanning the enhanced suffix array backwards to avoid the processing of suffixes that are not suffix-prefix matchings. Performance tests with real data showed that our new algorithm is 2.6 faster and uses about 15% less memory on the average.

O problema de todos os casamentos sufixo-prefixo é bem conhecido. O problema foi resolvido de forma ótima usando árvores de sufixos e vetores de sufixos. Neste trabalho apresentamos um outro algoritmo ótimo que supera os demais tanto em tempo quanto em memória. O novo algoritmo também usa vetores de sufixos aumentados, como o melhor algoritmo prático conhecido, de Ohlebusch e Gog (2010), mas percorre a estrutura de dados de forma diferente. Nosso algoritmo resolve o problema localmente para cada cadeia, percorrendo o vetor de sufixos do fim para o início, evitando o processamento de sufixos que não são casamentos sufixo-prefixo. Testes com dados reais mostraram que nosso algoritmo é 2.6 vezes mais rápido e usa em torno de 15% menos memória em média.

The Eternal Dominating Set problem (EDSP) was introduced by Goddard, Hedetniemi, and Hedetniemi [1], and was included in the class of graph protection problems [2]. The EDSP has been studied for several classes of graphs. Moreover, various bounds on the optimum of the problem have been established. In this talk, we present a computational evaluation of some of these bounds.

Reference(s):
[1] W. Goddard, S. Hedetniemi, and S. Hedetniemi. Eternal security in graphs. J. Combin. Math. Combin. Comput., volume 52, pages 169–180, 2005.
[2] W. F. Klostermeyer and C. M. Mynhardt. Protecting a graph with mobile guards. arXiv preprint arXiv:1407.5228, 2014.

This presentation is based on the article of same name presented and published in the proceedings of conference EUROCRYPT 2010 by Marten van Dijk from MIT Computer Science and Artificial Intelligence Laboratory and Craig Gentry, Shai Halevi, Vinod Vaikuntanathan from IBM Research (Advances in Cryptology – EUROCRYPT 2010 Lecture Notes in Computer Science Volume 6110, 2010, pp 24-43, Springer).
Authors proposed on this article a new simple fully homomorphic scheme using only elementary modular arithmetic. As the authors define: “The main appeal of our scheme is the conceptual simplicity”. Even using operations which are easy to implement and light in resources consumption to compute, proposed encryption schema remains not practical to achieve security levels compatible with the current demand. It is due required size of integers (GBytes) and number of elements in the public key. The construction explains most of the main problems that homomorphic encryption faces with and explores solutions for them.
The objective of this presentation is to expose the basic concepts of cryptography algorithms and homomorphic encryption applying them to understand the construction of the homomorphic encryption scheme proposed by the authors.

The presentation is based on the article of the same title presented by A. Efrat, A Itai and M. J. Katz. Given $A$ and $B$, two set of objects, the authors propose the bottleneck matching, a perfect matching that minimizes the weight of the edge with maximum weight, as a convenient way for measuring the resemblance between $A$ and $B$. Many cases are presented, in particular when the objects are points in the plane they obtain an efficient algorithm. In this talk, we present those results.

O problema de roteamento em arcos capacitado e aberto (Open Capacitated Arc Routing Problem, OCARP) é um problema NP-Difícil da classe de roteamento em arcos. Brevemente, dado um grafo não-direcionado $G(V,E)$ e funções de custo e demanda associadas a cada aresta em $E$, o problema consiste em encontrar um conjunto de rotas capacitadas de menor custo e que atendam às demandas de um subconjunto de arestas. As rotas no OCARP não são restritas a ciclos (rotas abertas) e podem iniciar e terminar em qualquer nó.
Nesta apresentação mostraremos uma formulação em Programação Linear Inteira e uma meta-heurística de Algoritmos Genéticos para o problema. Finalmente, serão apresentados resultados preliminares da heurística desenvolvida.

Este seminário apresenta o trabalho de Martens et al.[2], que introduz uma variação do jogo Lights Out, abordando o problema para classes de grafos. Nesta variação, dado um grafo $G$ munido de uma coloração de vértices $c:V(G) \rightarrow {0, 1, 2}$, o jogo consiste em remover de $G$ um vértice de cor 1 ou 2 e somar um à cor de todos os seus adjacentes (soma módulo 3). O processo é repetido até que não se possa realizar mais movimentos e o jogo é ganho se todos os vértices são removidos.

Referência(s):
[1] D. Hooper. Graph domination and the lights out puzzle. Washington State University, 2001
[2] J. Martens, L. McGee, C. Santos, and L. Sparrgrove. A variations of Lights Out, modulo 3. 2001

The Online Prize-Collecting Facility Location problem (OPFL) is an online version of the Prize-Collecting Facility Location problem (PFL).
The PFL is a generalization of the Uncapacitated Facility Location problem (FL) in which some clients may be left unconnected by paying a penalty. Another way to think about it is that every client has a prize that can only be collected if it is connected to some facility. In this presentation I show a primal-dual $O(\log{n})$-competitive algorithm for the OPFL, based on a previous algorithm for the Online Facility Location problem (OFL), and its competitive analysis.

We consider the following problem: given a non-negatively weighted simple undirected graph and a positive integer $K$, is there a realization of its vertices in the Euclidean space of dimension $K$ such that the Euclidean length corresponding to each edge is equal to its given weight? We show that for Henneberg type $I$ graphs the set $X$ of realizations is finite (up to congruences), and its cardinality and structure are intimately linked to a certain subgroup of automorphisms of $X$ generated by partial reflections. This also yields, as a consequence, some results on the fixed parameter tractability of a branching search method for computing $X$. This problem arises in structural biology, sensor network localization, clock synchronization, and other engineering fields. Moreover, Henneberg type I graphs turn out to be a good model for atomic proximity in protein backbones.

We present an efficient algorithm to find a realization of a (full) $n \times n$ squared Euclidean distance matrix in the smallest possible dimension. Most existing algorithms work in a given dimension: most of these can be transformed to an algorithm to find the minimum dimension, but gain a logarithmic factor of $n$ in their worst-case running time. Our algorithm performs cubically in $n$ (and linearly when the dimension is fixed, which happens in most applications).

In this work we propose a protocol combining a Physical Unclonable Function (PUF) with Password-based Authenticated Key Exchange (PAKE). The resulting protocol provides mutual multifactor authentication between client and server and establishes a session key between the authenticated parties, important features that were not found simultaneously in the literature of PUF-based authentication. The combination can be adapted to support a panic password which allows the client to notify the server in case of emergency. Moreover, a novel protocol for two-factor transaction authentication is proposed. This ensures that only parties authenticated in the current session can realize valid bank transactions.

Neste projeto investigamos uma variante do Problema de Roteamento de Veículos com Pickup e Delivery e com a restrição de que a cobertura dos vértices deve formar ciclos.
Estudamos tanto o caso em que os pontos dos vértices podem ser cobertos de forma desordenada, isto é, não importa a ordem em que o vértice de coleta e de entrega é visitado; como o caso com restrição quanto à ordem em que os vértices de coleta e entrega devem ser cobertos.
Provamos que as duas variantes do problema são NP-Difíceis e investigamos soluções aproximadas para o problema.
Estudando o problema do ponto de vista da Teoria dos Jogos Colaborativa, tratamos cada par coleta-entrega como um agente de um jogo de minimização de custo e maximização de lucro. Desta forma investigamos possíveis precificações para cada agente, verificando se o jogo definido tem alguma precificação que está no núcleo, ou seja, que todos os jogadores tenham motivação para formar uma coalizão e colaborar.

Neste seminário mostramos como construir a transformada Burrows-Wheeler (BWT) e o vetor de prefixos comuns mais longos (LCP) usando memória constante. A construção dessas estruturas é de grande importância para o desenvolvimento de soluções práticas em indexação e compressão. Embora nosso algoritmo seja quadrático, ele é construído explorando propriedades interessantes da BWT e do LCP e contrubui para avançar os resultados teóricos na área. Além disso, é um algoritmo simples, cuja implementação em C ocupa apenas uma página.

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 to 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 (Hammer, 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.)

Seja $\mathcal{C} $ um conjunto de circuitos orientados de um digrafo simples $D$. Dizemos que $\mathcal{C}$ gera $D$ se $\cup_{C \in \mathcal{C}} A(C) = A(D)$. Em 1963, Tibor Gallai conjecturou que todo digrafo fortemente conexo pode ser gerado por $\alpha(D)$ circuitos orientados, onde $\alpha(D)$ denota a cardinalidade do maior conjunto independente de $D$. Em 2007, Stéphane Bessy e Stéphan Thomassé [1] apresentaram uma elegante demonstração para essa conjectura, que será apresentada neste seminário.

Referência(s):
[1] Stéphane Bessy e Stéphan Tomassé. Spanning a Strong Digraph By $\alpha$ circuits: A proof of Gallai’s conjecture. Combinatorica 27 (6) (2007). 659-667.

Dado um grafo, queremos encontrar uma árvore geradora $T$, tal que o número de vértices internos de $T$ seja máximo. Sabe-se que esse problema é NP-difícil e era conhecido um algoritmo com fator de aproximação 2 para o caso geral. Neste seminário será apresentado um algoritmo de busca local $5/3$-aproximado de Knauer e Spoerhase [1] para esse problema.

Referência(s):
[1] Martin Knauer e Joachim Spoerhase. Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem. Algorithmica (2015) 71:797–811.

A estrutura Gema é uma estrutura de dados que pode ser usada para representar a topologia de triangulações. Sua vantagem está em sua simplicidade, sua eficiência e em sua generalização para qualquer dimensão $N$. Entretanto, ela só pode ser usada se a triangulação for colorível com $N+1$ cores nos vértices. Este trabalho consiste em propor algoritmos para subdividir um mapa de dimensão $N$ em uma triangulação $N+1$ colorida. Resultados para dimensões $N=2$ e $N=3$ serão apresentados.

Considere um conjunto de n robôs representados por pontos em um plano. Inicialmente somente um robô está ativo e os demais estão dormindo (stand-by) esperando serem acordados por algum outro robô. O objetivo é acordar todos os robôs o mais rápido possível, ou seja, minimizar o tempo para que todos os robôs estejam ativos. Para acordar um robô que esteja dormindo, um robô ativo tem que se mover até a localização de outro robô, que esteja dormindo, para ativá-lo. Uma vez ativado, este novo robô também pode ajudar a acordar os demais robôs restantes que estejam dormindo. Este é o problema em ainda em aberto no campo da Geometria Computacional, e esse trabalho tem como objetivo abordar sobre o assunto além de propor uma nova heurística para o problema: “Heurística Balanceada”.

O Problema do Caixeiro Viajante (TSP – Traveling Salesman Problem) consiste em, dado um grafo $G = (V,E)$ e custos $c \in Q$, para cada aresta $e \in E$, determinar um circuito hamiltoniano $C$ que minimize o custo $c(C)$. O TSP Euclidiano é uma variação deste problema original, onde os vértices de $V$ correspondem a pontos no plano Euclidiano e o custo das arestas $c$ correspondem a distância euclidiana entre os pontos correspondentes aos vértices no plano. Com base no artigo de [Arora 1998], que apresentou pela primeira vez um esquema de aproximação de tempo polinomial (PTAS) para o Problema do Caixeiro Viajante Euclidiano (Euclidean TSP), e nos trabalhos de [Schultes 2004] e [Williamson e Shmoys 2011], que descrevem o processo de forma mais intuitiva, será reproduzido durante esta apresentação uma maneira aproximada e executável em tempo polinomial de se resolver o TSP euclidiano (por programação dinâmica). A técnica utilizada para a solução aproximada deste problema ganha em importância, uma vez que ela é largamente aplicável a problemas no plano euclidiano. Exemplos são o problema da árvore de Steiner e o problema dos k-medianos para instâncias euclidianas.

O problema do Black and White Bin Packing é uma variação do problema Bin Packing (Empacotamento), onde dado uma quantidade de objetos de tamanhos variados definidos, procura-se empacotar todos os produtos em uma quantidade mínima de “bins” (contêineres), que por sua vez possuem capacidades limitadas. No Black and White Bin Packing, adiciona-se mais uma restrição de empacotamento, onde um item de uma cor qualquer (preto ou branco) não pode ser empacotado em um contêiner onde o último objeto lá empacotado foi da mesma cor do item que se deseja empacotar.
O artigo apresentado por János Balogh, József Békési, Gyorgy Dosa, Hans Kellerer, Zsolt Tuza (2013), analisa as versões Online, Offline e Restricted Offline para o problema e mostra limites inferiores e superiores de alguns algoritmos de empacotamento conhecidos (Next-Fit, First-Fit, Best-Fist, Worst-Fit, Any-Fit), e também apresenta um algoritmo Online 3-competitivo para o B&W-BP.