What makes a hard problem hard? In this talk, we approach some intriguing aspects of graph edge-colouring, a challenging combinatorial problem with many applications in network protocols and task scheduling in industry. By the celebrated Vizing’s Theorem of 1964, the minimum number of colours needed to properly colour the edges of any graph G is either the maximum degree Δ of G or it is Δ + 1. However, deciding between these two possibilities is an NP-hard problem, even when restricted to perfect graphs and further graph classes wherein other hard graph-theoretical problems, such as vertex-colouring, become easy (that is, polynomial). Notwithstanding, a probabilistic result by Erdős of 1977 brings that edge-colouring is a hard problem only for a set S to which almost no graph belongs. A recent result of ours extends Vizing’s proof for his theorem in order to show that even inside the set S edge-colouring is hard for almost no graph.

In this talk, I will present the article written by Michael Fellows, Bart Jansen and Frances Rosamond, which discusses what the authors refer to as the “Parameter ecology program”. Parameterized complexity starts from the premise that there are usually secondary measurements that can significantly affect the computational complexity of classical problems. The paper surveys several different parameters, their relationships and limitations. Also, it establishes a new race in the parameterized analysis of problems, with the purpose of uncovering the boundaries of tractability by finding the smallest possible parameterizations which admit FPT-algorithms or polynomial kernels. The computational intractability which inevitably emerges can be deconstructed by introducing additional parameters, leading towards a theory of fully multivariate algorithmics.

Problemas envolvendo ciclos hamiltonianos são diversos e numerosos em Teoria de Grafos. Vamos abordar uma conjectura a respeito de ciclos hamiltonianos em uma classe especial de grafos: os hipercubos. A Conjectura de Ruskey e Savage, 1993, afirma que qualquer emparelhamento em um hipercubo pode ser estendido para um ciclo hamiltoniano. Em 1996, Kreweras propôs a restrição desta conjetura aos emparelhamentos perfeitos e essa versão particular ficou conhecida como Conjectura de Kreweras. No artigo que vamos apresentar, Fink prova a Conjetura de Kreweras.

Nesta apresentação irei apresentar um algoritmo de Branch-and-Cut-and-Price para o Problema do Roteamento de Veículos Capacitados, que possui diversas aplicações para as áreas de logística e de roteirização. Nessa abordagem, proposta por Fukasawa et. al, utilizamos uma formulação em programação linear inteira que usa um número exponencial de variáveis e de restrições. Para resolver um modelo tão complexo, combinamos algoritmos de Branch-and-Cut com o procedimento de geração de colunas, obtendo assim um algoritmo de Branch-and-Cut-and-Price. A nossa implementação foi feita utilizando o framework de programação linear inteira SCIP e o solver CPLEX. Os experimentos indicam que o modelo de Branch-and-Cut-and-Price trouxe uma melhoria significativa no desempenho quando comparado com o modelo de Branch-and-Cut.

Several problems in Matching Theory can be “reduced” to special graph classes called ‘bricks’ (nonbipartite) and ‘braces’ (bipartite); it is for this reason that researchers started to deeply investigate the structure of these graphs. Perhaps the most famous example is the problem of deciding whether a given graph is ‘Pfaffian’ or not. The bipartite case of this problem is known to be polynomial-time solvable due to the groundbreaking works of McCuaig-Robertson-Seymour-Thomas (STOC 1997).

A connected bipartite graph $G$ is a brace if it has a matching of size two, and if each such matching extends to (i.e., is a subset of) a perfect matching of $G$. The smallest braces are $C_4$, $K_{3,3}$ and the cube graph. In fact, every 3-regular bipartite graph is a brace. McCuaig established a generation theorem for braces (2001), and used this as the principal induction tool to give a complete structural characterization of ‘Pfaffian’ braces (2004); this characterization yields a polynomial-time algorithm to decide whether a given bipartite graph is
‘Pfaffian’ or not. Robertson-Seymour-Thomas (1999) obtained the same characterization using a different approach.

A minimal brace is a brace $G$ such that deleting any edge results in a graph that is not a brace. During my recent visit to UFMS (Campo Grande), in a joint work with Marcelo H. de Carvalho and Phelipe A. Fabres, we derived an induction tool for minimal braces (from the aforementioned brace generation theorem of McCuaig). As an application, we prove that if $G$ is a minimal brace with $2n \geq 12$ vertices and $m$ edges then $m \leq 5n − 10$; furthermore, we give a complete characterization of minimal braces that meet this upper bound.

In this talk, I will present our results mentioned in the preceding paragraph. I will not present any lengthy proofs. I will not assume any background in Matching Theory. The talk will be self-contained. For more information, please see arxiv.org/abs/1903.11170.

Neste trabalho, Adamczyk et. al. estudam o capacitated $k$-median, um dos problemas de otimização em que a existência de um algoritmo de aproximação em tempo polinomial sem violação de capacidades ainda é um problema em aberto. Além disso, quando parametrizado pelo número de instalações, o problema é W[2]-difícil. Contornando ambas dificuldades, é dado um algoritmo de aproximação parametrizado com fator constante, sem violação de capacidades.

Kernels were defined by von Neumann and Morgenstern in the game theory field to study social and economic behaviour. Further developments in the area established it as an interesting field of study in the context of graph theory because of its relation to the, now proven true, Perfect Graph Conjecture. A seminal result is Richardson’s Theorem, which states that digraphs without odd cycles are kernel-perfect (every induced subdigraph has a kernel). Several generalizations of Richardson’s Theorem were proven, all regarding the existence of chords in odd cycles. In this talk I will present the main results in kernel theory that relate the existence of chords to the existence of kernels and provide an overview of the topic.

In this talk, we will discuss an alternative way to model Bin Packing and Cutting Stock Problems using directed graphs and arc flow. As a warmup, we will briefly go over Valério de Carvalho’s [1] arc-flow formulation for the one-dimensional Bin Packing Problem. This formulation was showed to be equivalent to the extensively studied column generation formulation of Gilmore and Gomory [2] in terms of the bound given by the linear relaxation. In the main portion of this presentation, we will present a more recent result by Brandão and Pedroso [3] in which the arc-flow model is generalized for the multidimensional Vector Bin Packing Problem along with symmetry breaking and graph compression algorithms that are showed to drastically improve the solver’s performance in practice.

Reference(s):
[1] J. M. Valério de Carvalho. Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research, 86 (1999)
[2] P. C. Gilmore and R. E. Gomory. A linear programming approach to the cutting-stock problem. Operations Research, 9 (1961)
[3] F. Brandão, J. P. Pedroso. Bin packing and related problems: General arc-flow formulation with graph compression. Computers & Operations Research, 69 (2016)

Nessa apresentação será visto o conceito de homeomorfismo, que pode ser visto como uma generalização de isomorfismo, e sua relação com colorações próprias. Além disso, será introduzido o assunto de coloração orientada e apresentado alguns problemas relacionados a este tipo de coloração.

A deadlock occurs in a distributed computation if a group of processes wait indefinitely for resources from each other. We study actions to be taken after deadlock detection, especially the action of searching for a small deadlock-resolution set. More precisely, given a “snapshot” directed graph $G$ representing a deadlocked state of a distributed computation governed by a certain deadlock model $M$, we investigate the complexity of vertex/arc deletion problems that aim at finding minimum vertex/arc subsets whose removal turns $G$ into a deadlock-free graph (according to model $M$). We present a computational complexity mapping considering the particular combination of deletion operations and deadlock models. A special attention is given to vertex removals in the OR model, called Knot-free Vertex Deletion, which consists of determining whether $G$ has a subset $S \subseteq V(G)$ of size at most $k$ such that $G[V \setminus S]$ contains no knot. A knot in a directed graph $G$ is a strongly connected subgraph $Q$ of $G$ with size at least two, such that no vertex in $V(Q)$ is an in-neighbor of a vertex in $V(G) \setminus V(Q)$. We present a parameterized complexity analysis of Knot-free Vertex Deletion. Such a graph problem has natural application in deadlock resolution, and it is closely related to Directed Feedback Vertex Set.
We prove that:
- Knot-free Vertex Deletion is $W[1]-hard$ when parameterized by the size of the solution; it can be solved in $2^{k \log \varphi}.n^{\mathcal{O}(1)}$ time, but assuming SETH it cannot be solved in $(2-e)^{k \log \varphi}.n^{o(1)}$ time, where $\varphi$ is the size of the largest strongly connected subgraph of $G$;
- it can be solved in $2^{\phi}.n^{\mathcal{O}(1)}$ time, but assuming ETH it cannot be solved in $2^{o(\phi)}.n^{\mathcal{O}(1)}$ time, where $\phi$ is the number of vertices with out-degree at most $k$;
- unless $NP \subseteq coNP/poly$, Knot-free Vertex Deletion does not admit polynomial kernel even when $\varphi=2$ and $k$ is the parameter;
- it can be solved in $2^{\mathcal{O}(tw)}.n^{\mathcal{O}(1)}$ time, but assuming ETH it cannot be solved in $2^{o(tw)}.n^{\mathcal{O}(1)}$ time, where $tw$ is the treewidth of the underlying undirected graph;
-it is in $FPT$ when parameterized by cliquewidth.
Joint work with Alan Carneiro and Fábio Protti.

Uma coloração arco-íris de um grafo conexo $G$ é uma coloração de arestas, não necessariamente própria, tal que entre qualquer par de vértices de $G$ existe um caminho cujas cores das arestas são duas a duas distintas. O número de conexão arco-íris de um grafo $G$, denotado por $rc(G)$, é o menor número de cores necessárias para se obter uma coloração arco-íris de $G$. Um grafo $G$ é arco-íris crítico se a remoção de uma aresta qualquer de $G$ aumenta o seu número de conexão arco-íris. Nesta palestra serão apresentados resultados conhecidos a respeito do número de conexão arco-íris e criticalidade arco-íris de algumas classes de grafos.

Um grafo potência de ciclo $C_n^k$ é um grafo obtido de um ciclo sem cordas $C_n$ adicionando arestas entre todos os vértices à distância de no máximo $k$.
Uma conjectura notável, proposta por Campos e de Mello, estabelece que $C_n^k$ , com $2 \leq k \leq \left \lfloor{\frac{n}{2}}\right \rfloor$, é Tipo 2 se e somente se $n$ é ímpar e $n < 3 (k+1)$, caso contrário é Tipo 1. Neste trabalho, mostramos que todo grafo potência de ciclo com $k$ par, $k \geq 2$ e $n \geq 4k^2 + 2k$ é Tipo 1. Além disso, classificamos todos os grafos potência de ciclo $C_n^k$, com $k = 3$ e $k = 4$ e também obtemos um limitante para que os grafos potência de ciclo $C_n^k$, com $k = 5$ e $k = 7$, sejam Tipo 2. Também apresentamos um algoritmo para gerar uma coloração harmônica equilibrada para os grafos potência de Ciclo $C_n^k$, com $n$ par ou $n$ ímpar e $n > 3(k+1)$, em um passo necessário para a construção de uma coloração total equilibrada Tipo 1. Por fim, apresentamos uma família infinita de grafos potência de ciclo em que a coloração total equilibrada é ótima.
Nesta apresentação também abordarei as principais diretrizes para possíveis trabalhos futuros.

One of the most fundamental classes of problems in computational geometry is the one dealing with the pairwise intersections among a set of n objects in the plane. Many of these problems can be reduced to the following one: “Given a set of n line segments in the plane, report all the intersecting pairs among them”. This problem arises in areas such as integrated circuit design, map overlay computation in geographic information systems, and collision detection in robotics. In this talk, we will discuss the results from the paper “Algorithms for Reporting and Counting Geometric Intersections” by Bentley and Ottmann (1979), which solves this problem with a $\mathcal{O}((n+k)\lg{n})$ algorithm (where $k$ is the number of intersections) that uses an important paradigm in computational geometry, the “sweep line” technique.

In the Cable-Trench Problem (CTP), the objective is to find a rooted spanning tree of a weighted graph that minimizes the length of the tree, scaled by a non-negative factor τ , plus the sum of all shortest-path lengths from the root, scaled by another non-negative factor γ. This is an intermediate optimization problem between the Single-Destination Shortest Path Problem and the Minimum Spanning Tree Problem.
In this talk we present a 2.415-approximation for CTP and also introduce a more general version of CTP, the Generalized CTP (GCTP), in which some vertices need not be connected to the root, but may serve as cost-saving merging points. This variant also generalizes the Steiner Tree Problem and we present an 8.599-approximation algorithm for it. Before this paper, no constant approximation for the standard CTP was known.

One form of characterizing the expressiveness of a piecewise linear neural network is by the number of linear regions, or pieces, of the function modeled. In this talk, we investigate the number of linear regions that these networks can attain, both theoretically and empirically. We present upper and lower bounds for the maximum number of linear regions on rectifier and maxout networks and a method to perform exact counting of the number of regions by modeling the neural network as a mixed-integer linear program. These bounds come from leveraging the dimension of the space defining each linear region, and they indicate that a shallow network may define more linear regions than any deep network. We also show how to approximate the number of linear regions of a rectifier network with an algorithm for probabilistic lower bounds on the number of solutions of mixed-integer linear programs. This algorithm is several orders of magnitude faster than exact counting and the values reach similar orders of magnitude, hence making it a viable method to compare the expressiveness of such networks.

This talk is based on joint work with Christian Tjandraatmadja (Google) and Srikumar Ramalingam (The University of Utah / Google). The first paper has been presented at ICML 2018 (https://arxiv.org/abs/1711.02114) and the second is currently under review (https://arxiv.org/abs/1810.03370).

-Basic results about matching covered graphs involving separating cuts and tight cuts
-The characterization of graphs free of nontrivial tight cuts, by Edmonds, Lovász and Pulleyblank
-Characterizations of the Perfect Matching Polytope: the original by Edmonds, the restriction to separating cuts and to robust cuts
-Solid graphs and odd intercyclic graphs
-4-flows, the Integer Cone and the Matching Lattice
-Open Problems

A handout is available at my home page http://www.ic.unicamp.br/~lucchesi

-Basic results about matching covered graphs involving separating cuts and tight cuts
-The characterization of graphs free of nontrivial tight cuts, by Edmonds, Lovász and Pulleyblank
-Characterizations of the Perfect Matching Polytope: the original by Edmonds, the restriction to separating cuts and to robust cuts
-Solid graphs and odd intercyclic graphs
-4-flows, the Integer Cone and the Matching Lattice
-Open Problems

A handout is available at my home page http://www.ic.unicamp.br/~lucchesi

Após uma breve introdução à Teoria de Ramsey, em que apresentaremos alguns dos problemas estudados na área, analisaremos uma conjectura proposta por Bender e Wormald [1] a respeito de sub-árvores contidas em todo torneio suficientemente grande, e alguns problemas similares.
Trabalho feito em conjunto com Richard Mycroft.

Referência(s):
E. A. Bender, N. C. Wormald. Random trees in random graphs. Proceedings of the American Mathematical Society 103(1), 1988.

Um dos principais ingredientes para a resolução de problemas de programação inteira na prática é a utilização de planos de cortes genéricos. Dentre esses planos de corte, os cortes de Gomory são uns dos mais importantes.

Na primeira parte desta palestra, irei revisar um tipo de generalização dos cortes de Gomory, baseado em um conceito geométrico e alguns resultados interessantes relacionados. Na segunda parte, apresentarei um problema computacional que surge nesse contexto e o nosso algoritmo proposto para melhorar o desempenho desse problema. O nosso algoritmo obtem uma melhora de duas ordens de grandeza sobre os algoritmos que eram usados previamente.

A connected graph, on at least two vertices, is matching covered if each edge belongs to some perfect matching. Every matching covered graph may be decomposed (uniquely) into special matching covered graphs called bricks (which are nonbipartite) and braces (which are bipartite) — using the tight cut decomposition procedure.
For a brick $G$: (i) an edge $e$ is removable if $G - e$ is matching covered; furthermore, $e$ is b-invariant if the tight cut decomposition of $G - e$ yields exactly one brick, and it is quasi-b-invariant if the tight cut decomposition of $G - e$ yields exactly two bricks, (ii) a pair of edges $R := \{e, f\}$ is a removable doubleton if $G - R$ is bipartite and matching covered. A brick $G$ is near-bipartite if it has a removable doubleton; otherwise it is non-near-bipartite. (For example, the pentagonal prism is near-bipartite; it has 5 removable doubletons and 5 b-invariant edges. The Petersen graph is non-near-bipartite; each edge is quasi-b-invariant.)
Using standard matching theory results (such as Tutte’s Theorem and Edmonds’ characterization of the perfect matching polytope), it can be shown that every 2-edge-connected cubic graph is matching covered; furthermore, every essentially 4-edge-connected cubic graph is either a brick or a brace. (I will perhaps present a “polyhedral” proof of these facts.)
In 2002, Carvalho, Lucchesi and Murty proved the following conjecture of Lovasz: every brick, distinct from $K_4$, $\overline{C_6}$ and the Petersen graph, has a b-invariant edge.
Let $\mathcal{Q}$ denote the class of essentially 4-edge-connected cubic bricks. In a joint work with Carvalho, Lucchesi and Little, we proved the following. If $G$ is any member of $\mathcal{Q}$ then: (i) each edge of $G$ is either b-invariant, or is quasi-b-invariant, or otherwise participates in a removable doubleton; (ii) furthermore, if $G$ is non-near-bipartite, and if it is not the Petersen graph, then at least two-third of its edges are b-invariant.
What about the near-bipartite members of $\mathcal{Q}$? We also conjectured that, if $G$ is a near-bipartite member of $\mathcal{Q}$, and if it is not $K_4$, then at least one-third of its edges are b-invariant. This was recently proved by Lu, Feng and Wang.
I will discuss all of this, and mention some structural theorems and conjectures. Two graphs will play special roles — of course, the famous Petersen graph — and another beautiful graph called the Cubeplex that was first discovered by Fischer and Little (2001) in the context of Pfaffian orientations.
The talk will be mostly self-contained. I will assume only basic knowledge of graph theory. I will not present any lengthy proofs. For more details, see [1]. This talk will be in English.

Reference(s):
[1] Nishad Kothari, Marcelo H. de Carvalho, Cláudio L. Lucchesi, Charles H. C. Little. On essentially 4-edge-connected cubic bricks. arXiv:1803.08713

Um conjunto de vértices $D$ de um grafo $G = (V(G), E(G))$ é um conjunto dominante se todo vértice $v \in V(G)$ é um elemento de $D$ ou é adjacente a um elemento de $D$. A cardinalidade de um menor conjunto dominante de $G$ é chamada de número de dominação e é denotada por $\gamma(G)$. O problema de dominação em grafos consiste em determinar $\gamma(G)$ para um grafo arbitrário $G$. Em 1979, Garey e Johnson provaram que, dado um grafo $G$ e um inteiro $k$, decidir se $\gamma(G) \leq k$ é um problema NP-Completo. Pela importância teórica e prática dos problemas de dominação, sua NP-completude não arrefeceu o interesse dos pesquisadores e muitos resultados envolvendo este parâmetro têm sido obtidos em várias classes de grafos. Nesta apresentação serão discutidos os resultados do artigo “The domination number of cubic Hamiltonian graphs” de M. Cropper, D. Greenwell, A.J.W. Hilton e A. Kostochka (2005), o qual estabelece limites para o número de dominação em grafos cúbicos Hamiltonianos.

A path decomposition of a graph $G$ is a collection of edge-disjoint paths of $G$ that covers the edge set of $G$. Gallai (1968) conjectured that every connected graph on $n$ vertices admits a path decomposition of cardinality at most $\lceil \frac{n}{2} \rceil$. Seminal results towards its verification consider the graph obtained from $G$ by removing its vertices of odd degree, which is called the E-subgraph of $G$. Lovász (1968) verified Gallai’s Conjecture for graphs whose E-subgraphs consist of at most one vertex, and Pyber (1996) verified it for graphs whose E-subgraphs are forests. Let $G_{d, k}$ be the family of connected graphs such that (i) each block has maximum degree at most $d$ and (ii) at most $k$ blocks contain triangles. In 2005, Fan verified Gallai’s Conjecture for graphs whose E-subgraph belongs to $G_{3, 0}$. In this talk, we show how we generalized Fan’s result by verifying Gallai’s Conjecture for graphs whose E-subgraphs has maximum degree at most $3$ or it is a subgraph of a graph in $G_{3, 1}$.
This is a joint work with professor Fábio Botler from Federal Univesity of Rio de Janeiro.

In the classical Travelling Salesman Problem (TSP), one wants to find a route that visits a set of n cities, such that the total travelled distance is minimum. An often considered generalization is the Travelling Car Renter Problem (CARS), in which the route is travelled by renting a set of cars and the cost to travel between two given cities depends on the car that is used. The car renter may choose to swap vehicles at any city, but must pay a fee to return the car to its pickup location. This problem appears in logistics and urban transportation when the vehicles can be provided by multiple companies, such as in the tourism sector. We consider the case in which the return fee is some fixed number g ≥ 0, which we call the Uniform CARS. We show that, already for this version, there is no o(log n)-approximation algorithm unless P = NP. The main contribution is an O(log n)-approximation algorithm for the problem, which is based on the randomized rounding of an exponentially large LP-relaxation.

O problema de maximização de influência consiste em encontrar um subconjunto dos indivíduos de uma rede social de modo que, a partir deste subconjunto, seja possível propagar informações para o maior número de indivíduos. O propósito deste seminário é discutir um modelo de programação linear inteira para uma generalização deste problema proposta por Fischetti et. al. (2018). Uma das contribuições do artigo é uma heurística baseada no método de geração de colunas.

The Max-Cut problem consists of partitioning a set of $n$ nodes into two subsets so that the sum of the edges between the subsets is as large as possible. This work presents four versions of meta-heuristics algorithms, based on Genetic Algorithm and Simulated Annealing, which use a set of valid inequalities in their structure. To the best of our knowledge, we are the first to use valid inequalities in the construction of metaheuristics for the Max-Cut Problem. The results of the computational experiments show that the use of these inequalities causes the algorithms to obtain better results than the classical version, that is, without the inequalities and also, in some cases, competitive with the state of the art for Max-Cut.

O problema de reconfiguração de redes de distribuição de energia elétrica busca uma topologia para a rede que minimiza perdas técnicas (perdas resistivas).
Encontrar as configurações ótimas é um difícil problema de otimização combinatória que vem ganhando nova forma nas últimas décadas, decorrentes da introdução de geração distribuída ao longo da rede e de inovações complementares associadas ao conceito de Smart Grids.
Cavalheiro et al., 2018* discutiu as características e alternativas de solução para problema de otimização das configurações onde um pequeno número de fontes com características aleatórias e gerações significativas em relação ao total de cargas da rede. Sob essas condições, o trabalho mostra que as melhores configurações são aquelas que levam a minimização formal da esperança matemática das perdas, considerando a distribuição de probabilidades das injeções de energia. Para a solução do problema, os autores adotam o método BRKGA (biased random-key genetic algorithm).
Nesta apresentação será discutido o trabalho de Cavalheiro et al., 2018 e a continuação da pesquisa.

[*] E. M. Cavalheiro, A. H. Vergílio, and C. Lyra, “Optimal configuration of power distribution networks with variable renewable energy resources” Computers & Operations Research, vol. 96, pp. 272 – 280, 2018.

Geometric knapsack problems (GKP) are extensions of the classical knapsack problem to a geometric setting. Basically, given a set of distinct points, each one associated with a real value, we want to construct a simple polygon (a fence) that maximizes its net profit: the total value of the enclosed points minus the cost to build it. Some variants include: an upper bound on the total cost of the fence and whether the point values are unrestricted in sign or not. In this talk, we will discuss the results of the paper “Optimal Solutions for a Geometric Knapsack Problem” by Cano, de Souza and de Rezende (2018), which addresses the GKP version with point values unrestricted in sign and no bound on the fence cost, which turns out to be NP-Hard. The authors introduced an Integer Linear Programming model for the problem and applied it to hundreds of instances of two classes: one comprised of uniformly generated points with randomly assigned values; and another composed of convex layered points with value distribution biased towards concentrating negative-valued points on the innermost layers.

This talk will be in English.

In this talk I will present some of our results for the Balanced Connected $k$-Partition (BCPk) problem. The main focus of the talk will be the proofs that characterize some inequalities as facets. In order to make the talk accessible to those who have no previous experience with polyhedral combinatorics, I will try to give a short introduction to the some of the tools we use from Polyhedral Theory. This is joint work with professors Flávio K. Miyazawa, Phablo F. S. Moura and Yoshiko Wakabayashi. In BCPk we are interested in partitioning a vertex-weighted connected graph into $k$ connected subgraphs that have similar weights, for a fixed integer $k \geq 2$. More formally, given a connected graph $G$ with nonnegative weights on the vertices, we want to find a partition $\{V_1, …, V_k\}$ of $V(G)$, such that each class $V_i$, for $i = \{1, \ldots, k\}$, induces a connected subgraph of $G$, and the weight of a class with the minimum weight is as large as possible. It is known that BCPk is NP-hard even on bipartite graphs and on interval graphs. It has been largely investigated under different approaches and perspectives: exact algorithms, approximation algorithms for some values of $k$ or special classes of graphs, close variants of the problem, and inapproximability results. On the practical side, BCPk is used to model many applications arising in police patrolling, image processing, cluster analysis, operating systems and robotics. We show a formulation for BCPk with only binary variables and a potentially large number of constraints that can be separated in polynomial time. We present a polyhedral study of the polytope associated with this formulation, and characterize some of the inequalities as facets of the connected $k$-subpartition polytope. We also derived a lifting procedure and new inequalities, which can strengthen the formulation.

Nesta palestra, discutirei alguns resultados em complexidade clássica e parametrizada sobre o problema da $k$-Coloração de grafos-$(r, l)$. Um grafo-$(r, l)$ é tal que seu conjunto de vértices pode ser particionado em $r$ conjuntos independentes e $l$ cliques. Esta família generaliza grafos split, bipartidos e $r$-coloráveis (entre outras), e possui propriedades estruturais interessantes para serem estudadas sob o olhar da análise parametrizada. Os resultados apresentados são do aluno Matheus Alves e do Prof. Dr. Ueverton Souza da Universidade Federal Fluminense.

We discuss constructions and applications of two types of combinatorial arrays: orthogonal and covering arrays. Other combinatorial matrices have been similarly considered in the literature, including ordered orthogonal arrays, permutation arrays, frequency permutation arrays, hypercubes and Costas arrays. For more information, see the survey ``Finite Field Constructions of Combinatorial Arrays’’ by L. Moura, G. Mullen and D. Panario (Designs, Codes and Cryptography, 2016). In this talk we briefly explain the constructions and focus on the concepts and applications of these arrays.

An Orthogonal Array (OA) of strength $t$ on $v$ symbols is an array with the property that, for every $t$-combination of column vectors, every one of the possible $v^t$ $t$-tuples of symbols appears as a row “exactly’’ once in the subarray defined by these column vectors. OAs have been applied in coding theory and in cryptography. They are equivalent to MDS (maximum distance separable) codes where the strength of the OA is closely related to the minimum distance of the code. OAs are also closely related to secret sharing in cryptography, as we will exemplify.

Similarly, a Covering Array of strength $t$ on $v$ symbols is an array with the property that, for every $t$-combination of column vectors, every one of the possible $v^t$ $t$-tuples of symbols appears as a row “at least’’ once in the subarray defined by these column vectors. Covering arrays are used to reduce the number of tests in application areas such as software testing and group testing. Example of these applications will be provided.

A common theme on several of the recent constructions of these arrays is the use of linear feedback shift register (LFSR) sequences and finite fields. Arrays whose rows are cyclic shifts of a sequence over a finite field possess many combinatorial properties. They have been used to build arrays attaining a high number of $t$-subsets of columns with the desired “coverage property’’.

A Genome Rearrangement is a large scale mutation that changes the position and the orientation of conserved regions in a genome. In the field of comparative genomics, one common approach to estimate the evolutionary distance is to formulate it as the minimum number of rearrangements that transforms a genome into another, which is called rearrangement distance. In the past decades, these problems were studied considering many types of rearrangements (such as reversals, transpositions, transreversals, and revrevs) and considering the same weight for all rearrangements, or different weights depending on the types of rearrangements. We discuss known results about the complexity of the problems involving reversals and transpositions, and we present new results for the models including transpositions alongside reversals, transreversals, and revrevs. Furthermore, we address a cost function related to the number of fragmentations caused by a rearrangement, proving that the problem of finding a minimum cost sorting sequence, considering the fragmentation cost function, is NP-hard for transpositions and the combination of reversals and transpositions.

Problemas de Coloração (de faces, vértices ou arestas) em grafos são amplamente conhecidos; em particular o famoso e folclórico Teorema das Quatro Cores, cuja demonstração desafiou e instigou pesquisadores por mais de um século.
Já os problemas em fluxos inteiros são bem menos conhecidos, embora relacionados. O célebre William T. Tutte definiu (antes da primeira demonstração do Teorema das Quatro Cores) o conceito de fluxos inteiros como uma forma de generalizar para grafos não necessariamente planares o conceito de coloração de faces. Também propôs três conjecturas, ainda abertas, que generalizam teoremas sobre coloração de grafos planares. Assim, o tema de fluxos inteiros trata-se de um tópico bastante desafiante, mas também repleto de teoremas que são verdadeiras jóias por correlacionar vários belos problemas em Teoria dos Grafos. Nesta palestra será dada uma introdução ao tema, com a apresentação dos principais resultados conhecidos neste tópico e dando uma ideia das principais técnicas conhecidas.