Ueverton dos Santos Souza

Given a finite, non-increasing degree sequence, the Graph Realization problem asks whether a labeled simple graph realizes it. We study its generalization with prescribed sizes for selected nontrivial edge cuts. Let w be the maximum size of a constrained vertex set. We prove polynomial-time solvability when w <= 3 and any two constrained triples intersect in at most one vertex. Without that intersection condition, the problem is NP-complete already for w = 3, even when every required degree is 1 or 3. It is also NP-complete for w = 4 when all larger constrained sets are pairwise disjoint, and every required degree equals 1. Finally, for w <= 6, we prove NP-completeness even when the realization must be a subgraph of a union of 6-cycles. These results establish sharp complexity boundaries governed by constraint width and intersection structure.

Maximum Minimal Set Cover é a variante max-min do clássico problema Set Cover, cujo objetivo é encontrar um set cover minimal de cardinalidade máxima. Este problema generaliza Max Min Vertex Cover e Upper Domination. Embora (Maximum Minimal) Set Cover e (Maximum Minimal) Hitting Set sejam equivalentes sob certos parâmetros, diferenças surgem quando o tamanho do universo, denotado por n, é considerado. Maximum Minimal Hitting Set admite trivialmente um algoritmo em tempo O∗(2n), mas uma análise exaustiva para Maximum Minimal Set Cover demanda tempo O∗(2m), onde m é o número de conjuntos. Como m pode ser muito maior que n, investigamos algoritmos exatos exponenciais em função de n para o problema. Mostramos que Maximum Minimal Set Cover pode ser resolvido em tempo O∗(2n) e que um algoritmo subexponencial de tempo O∗(2o(n)) implicaria a falsidade da ETH. Por fim, generalizamos os resultados anteriores apresentando um algoritmo em tempo O∗ (2k), onde k é o tamanho do vertex cover mínimo do grafo de incidência, além de um limite inferior mais apertado baseado na SETH.

Genome rearrangement has been an active area of research in computational comparative genomics for the last three decades. While initially mostly an interesting algorithmic endeavor, now the practical application of rearrangement distance methods and more advanced phylogenetic tasks is becoming common practice, given the availability of many completely sequenced genomes. Several genome rearrangement models have been developed over time, sometimes with surprising computational properties. A prominent example is the fact that computing the reversal distance of two signed permutations is possible in linear time, while for two unsigned permutations it is NP-hard. Therefore one has to always be careful about the precise problem formulation and complexity analysis of rearrangement problems in order not to be fooled. The double distance is the minimum number of genomic rearrangements between a singular and a duplicated genome that - in addition to rearrangements - are separated by a whole genome duplication. At the same time it allows to assign the genes of the duplicated genome to the two paralogous chromosome copies that existed right after the duplication event. Computing the double distance is another example of a tricky hardness landscape: If the distance measure underlying the double distance is the simple breakpoint distance, the problem can be solved in linear time, while with the more elaborate DCJ distance it is NP-hard. Indeed, there is a whole family of distance measures, parameterized by an even number k, between the breakpoint distance (k = 2) at the one end and the DCJ distance (k = ∞) at the other end. Only little was known about the hardness border that lies somewhere on the way between these two extremes. Precisely, beneath the two border cases the (linear) problem complexity was known only for k = 4 and k = 6. In this paper we close the gap, giving a full picture of the hardness landscape when computing the double distance.

AMC is a journal published by University of Primorska.