Dans cette thèse, nous considérons plusieurs paramètres des hypergraphes et nous étudions si les restrictions aux sous-classes des hypergraphes permettent d’obtenir des propriétés combinatoires et algorithmiques souhaitables. La plupart des paramètres que nous prenons en compte sont des instances spéciales des packings et transversals des hypergraphes.Dans la première partie, nous allons nous concentrer sur les line graphs des graphes subcubiques sans triangle et nous allons démontrer que pour tous ces graphes il y a un independent set de taille au moins 3|V(G)|/10 et cette borne est optimale. Conséquence immédiate: nous obtenons une borne inférieure optimale pour la taille d’un couplage maximum dans les graphes subcubiques sans triangle. De plus, nous montrons plusieurs résultats algorithmiques liés au FEEDBACK VERTEX SET, HAMILTONIAN CYCLE et HAMILTONIAN PATH quand restreints aux line graphs des graphes subcubiques sans triangle.Puis nous examinons trois hypergraphes ayant la propriété d’Erdős-Pósa et nous cherchons à déterminer les fonctions limites optimales. Tout d’abord, nous apportons une fonction theta-bounding pour la classe des graphes subcubiques et nous étudions CLIQUE COVER: en répondant à une question de Cerioli et al., nous montrons qu’il admet un PTAS pour les graphes planaires. Par la suite, nous nous intéressons à la Conjecture de Tuza et nous montrons que la constante 2 peut être améliorée pour les graphes avec arêtes contenues dans au maximum quatre triangles et pour les graphes sans certains odd-wheels. Enfin, nous nous concentrons sur la Conjecture de Jones: nous la démontrons dans le cas des graphes sans griffes avec degré maximal 4 et nous faisons quelques observations dans le cas des graphes subcubiques.Nous étudions ensuite la VC-dimension de certains hypergraphes résultants des graphes. En particulier, nous considérons l’hypergraphe sur l’ensemble des sommets d’un certain graphe qui est induit par la famille de ses sous-graphes k-connexes. En généralisant les résultats de Kranakis et al., nous fournissons des bornes supérieures et inférieures optimales pour la VC-dimension et nous montrons que son calcul est NP-complet, pour chacun k > 0. Enfin, nous démontrons que ce problème (dans le cas k = 1) et le problème étroitement lié CONNECTED DOMINATING SET sont soit solvables en temps polynomial ou NP-complet, quand restreints aux classes de graphes obtenues en interdisant un seul sous-graphe induit.Dans la partie finale de cette thèse, nous nous attaquons aux meta-questions suivantes: Quand est-ce qu’un certain problème “difficile” de graphe devient “facile”?; Existe-t-il des frontières séparant des instances “faciles” et “difficiles”? Afin de répondre à ces questions, dans le cas des classes héréditaires, Alekseev a introduit la notion de boundary class pour un problème NP-difficile et a montré qu’un problème Pi est NP-difficile pour une classe héréditaire X finiment défini si et seulement si X contient un boundary class pour Pi. Nouscontinuons la recherche des boundary classes pour les problèmes suivants: HAMILTONIAN CYCLE THROUGH SPECIFIED EDGE, HAMILTONIAN PATH, FEEDBACK VERTEX SET, CONNECTED DOMINATING SET and CONNECTED VERTEX COVER. / In this thesis, we consider several hypergraph parameters and study whether restrictions to subclasses of hypergraphs allow to obtain desirable combinatorial or algorithmic properties. Most of the parameters we consider are special instances of packings and transversals of hypergraphs.In the first part, we focus on line graphs of subcubic triangle-free graphs and show that any such graph G has an independent set of size at least 3|V(G)|/10, the bound being sharp. As an immediate consequence, we obtain a tight lower bound for the matching number of subcubic triangle-free graphs. Moreover, we prove several algorithmic results related to FEEDBACK VERTEX SET, HAMILTONIAN CYCLE and HAMILTONIAN PATH when restricted to line graphs of subcubic triangle-free graphs.Then we consider three hypergraphs having the Erdős-Pósa Property and we seek to determine the optimal bounding functions. First, we provide an optimal theta-bounding function for the class of subcubic graphs and we study CLIQUE COVER: answering a question by Cerioli et al., we show it admits a PTAS for planar graphs. Then we focus on Tuza’s Conjecture and show that the constant 2 in the statement can be improved for graphs whose edges are contained in at most four triangles and graphs obtained by forbidding certain odd-wheels. Finally, we concentrate on Jones’ Conjecture: we prove it in the case of claw-free graphs with maximum degree at most 4 and we make some observations in the case of subcubic graphs.Then we study the VC-dimension of certain set systems arising from graphs. In particular, we consider the set system on the vertex set of some graph which is induced by the family of its k-connected subgraphs. Generalizing results by Kranakis et al., we provide tight upper and lower bounds for the VC-dimension and we show that its computation is NP-complete, for each k > 0. Finally, we show that this problem (in the case k = 1) and the closely related CONNECTED DOMINATING SET are either NP-complete or polynomial-time solvable when restricted to classes of graphs obtained by forbidding a single induced subgraph.In the final part of the thesis, we consider the following meta-questions: When does a certain “hard” graph problem become “easy”?; Is there any “boundary” separating “easy” and “hard” instances? In order to answer these questions in the case of hereditary classes, Alekseev introduced the notion of a boundary class for an NP-hard problem and showed that a problem Pi is NP-hard for a finitely defined (hereditary) class X if and only if X contains a boundary class for Pi. We continue the search of boundary classes for the following problems: HAMILTONIAN CYCLE THROUGH SPECIFIED EDGE, HAMILTONIAN PATH, FEEDBACK VERTEX SET, CONNECTED DOMINATING SET and CONNECTED VERTEX COVER.

Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2015-10-27T14:37:06Z No. of bitstreams: 2 Tese - Marcio Antonio Duarte - 2015.pdf: 457015 bytes, checksum: 1f57686628e44a0cebc1fee7aaf0bcfc (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-10-29T10:04:41Z (GMT) No. of bitstreams: 2 Tese - Marcio Antonio Duarte - 2015.pdf: 457015 bytes, checksum: 1f57686628e44a0cebc1fee7aaf0bcfc (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-10-29T10:04:41Z (GMT). No. of bitstreams: 2 Tese - Marcio Antonio Duarte - 2015.pdf: 457015 bytes, checksum: 1f57686628e44a0cebc1fee7aaf0bcfc (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-04-10 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / In this work, we present some related results, especially the properties algoritimics and of complexity of a product of graphs called complementary prism. Answering some questions left open by Haynes, Slater and van der Merwe, we show that the problem of click, independent set and k-dominant set is NP-Complete for complementary prisms in general. Furthermore, we show NP-completeness results regarding the calculation of some parameters of the P3-convexity for the complementary prism graphs in general, as the P3-geodetic number, P3-hull number and P3-Carathéodory number. We show that the calculation of P3-geodetic number is NP-complete for complementary prism graphs in general. As for the P3-hull number, we can show that the same can be efficiently computed in polynomial time. For the P3-Carathéodory number, we show that it is NPcomplete complementary to prisms bipartite graphs, but for trees, this may be calculated in polynomial time and, for class of cografos, calculating the P3-Carathéodory number of complementary prism of these is 3. We also found a relationship between the cardinality Carathéodory set of a graph and a any Carathéodory set of complementary prism. Finally, we established an upper limit calculation the parameters: geodetic number, hull number and Carathéodory number to operations complementary prism of path, cycles and complete graphs considering the convexities P3 and geodesic. / Neste trabalho, apresentamos alguns resultados relacionados, principalmente às propriedades algorítmicas e de complexidade de um produto de grafos chamado prisma complementar. Respondendo algumas questões deixadas em aberto por Haynes, Slater e van der Merwe, mostramos o problema de clique, conjunto independente e conjunto com kdominantes é NP-Completo para prismas complementares em geral. Além disso, mostramos resultados de NP-completude em relação ao cálculo de alguns parâmetros da convexidade P3 para o prisma complementar de grafos em geral, como o número P3, número envoltório P3 e número de Carathéodory. Mostramos que o cálculo do número P3 é NPcompleto para o prisma complementar de grafos em geral. Já para o número envoltório P3, mostramos que o mesmo pode ser calculado de forma eficiente em tempo polinomial. Para o número de Carathéodory, mostramos que é NP-completo para os prismas complementares de grafos bipartidos, mas que para árvores, este pode ser calculado em tempo polinomial e ainda, para classe dos cografos, o cálculo do número de Carathéodory do prisma complementar desses é 3. Encontramos também, uma relação entre a cardinalidade de um conjunto de Carathéodory de um grafo qualquer e um conjunto de Carathéodory do seu prisma complementar. Por fim, estabelecemos um limite superior do cálculo dos parâmetros: número geodésico, número envoltório e número de Carathéodory para operações prisma complementar de grafos caminho, ciclos e completos considerando as convexidades P3 e geodésica.

Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2016-07-13T15:19:52Z No. of bitstreams: 2 Dissertação - Elvis Edgard Inga de La Cruz - 2015.pdf: 4690319 bytes, checksum: fb5f7a5ba3966e716246274700bab6ae (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2016-07-14T11:29:19Z (GMT) No. of bitstreams: 2 Dissertação - Elvis Edgard Inga de La Cruz - 2015.pdf: 4690319 bytes, checksum: fb5f7a5ba3966e716246274700bab6ae (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2016-07-14T11:29:19Z (GMT). No. of bitstreams: 2 Dissertação - Elvis Edgard Inga de La Cruz - 2015.pdf: 4690319 bytes, checksum: fb5f7a5ba3966e716246274700bab6ae (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2015-08-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This study aimed, expand the method of Production Systems Sustainability Perception Rice High -MPSAT Lands. The choice of this method is justified by the fact that it has a good theoretical framework and be easily understood by the actors; however, it lacks nonparametric statistical approach. They were interviewed actors in the production chain of upland rice in Mato Grosso on two occasions, in 2006/07, when the MPSATA and 2014 was developed as part of this research. The methodology transformed the qualitative elements that make up the MPSATA (questions, attributes, indicators, key variables, secondary counselors, primary guiding and sustainability dimensions) for ordinal type and identified the sense of the order of the categories of these elements. Then it verified the significance of matched elements, considering the 2007 and 2014 surveys, with the IBM-SPSS 21. Later the element values were calculated. These elements have as a data source practices and managements carried out along the production chain. The end result of the research was the development of Parametric Method Not for Perception Sustainability Highlands Rice Production System - MPSATA-NP. The results obtained by MPSATA-NP allowed to accept or reject in statistical terms, if there were significant differences between the values of the features found in different eras who were surveyed, revealing that the 221 questions elements, eleven have statistical difference between their medians (three environmental dimension, two of the socioeconomic scale, four in the economic dimension and two territorial dimension). The other sustainability factors have changes compared to paired terms, however, it can´t be said that these elements are in fact different and represent more or less sustainable production conditions. So it follows that not hear significant change in the perception of the actors with respect to the sustainability of the land rice production system in the region. / O presente trabalho teve como objetivo, ampliar o método da Percepção de Sustentabilidade de Sistemas de Produção Arroz de Terras Altas -MPSAT1. A escolha desse método se justifica pelo fato do mesmo possuir uma boa estrutura teórica e ser de fácil compreensão pelos atores, no entanto, carece de abordagem estatística não paramétrica. Foram entrevistados atores da cadeia produtiva de arroz de terras altas em Mato Grosso em dois momentos, em 2006/07, quando o MPSATA foi desenvolvido e 2014, como parte integrante da presente pesquisa. A metodologia utilizada transformou os elementos qualitativos que compõem o MPSATA (quesitos, atributos, indicadores, variáveis essenciais, orientadores secundários, orientadores primários e dimensões de sustentabilidade) para o tipo ordinal e identificou o sentido da ordem das categorias desses elementos. Em seguida foi verificada a significância dos elementos emparelhados, considerando os levantamentos de 2007 e 2014, com o software IBM-SPSS 21. Posteriormente foram calculados os valores dos elementos. Estes elementos possuem como fonte de dados as práticas e manejos realizados ao longo da cadeia produtiva. O resultado final da pesquisa foi a elaboração do Método Não Paramétrico para a Percepção de Sustentabilidade de Sistema de produção de Arroz de Terras Altas – MPSATA-NP. Os resultados obtidos pelo MPSATA-NP permitiram aceitar ou rejeitar em termos estatísticos, se havia diferenças significativa entre os valores dos elementos quesitos encontrados nas diferentes épocas que foram pesquisados, revelando que dos 221 elementos quesitos, onze possuem diferença estatística entre as suas medianas (três da dimensão ambiental, duas da dimensão socioeconômica, quatro da dimensão econômica e dois da dimensão territorial). Os outros elementos de sustentabilidade possuem mudanças, no entanto, não pode-se se afirmar sejam de fato diferentes e que representem condições de produção mais ou menos sustentáveis. Assim, se conclui que não ouve mudança significativa na percepção dos atores com respeito à sustentabilidade do sistema de produção de arroz de terras na região.

Un code identifiant est un ensemble de sommets d'un graphe tel que, d'une part, chaque sommet hors du code a un voisin dans le code (propriété de domination) et, d'autre part, tous les sommets ont un voisinage distinct à l'intérieur du code (propriété de séparation). Dans cette thèse, nous nous intéressons à des aspects combinatoires et algorithmiques relatifs aux codes identifiants.Pour la partie combinatoire, nous étudions tout d'abord des questions extrémales en donnant une caractérisation complète des graphes non-orientés finis ayant comme taille minimum de code identifiant leur ordre moins un. Nous caractérisons également les graphes dirigés finis, les graphes non-orientés infinis et les graphes orientés infinis ayant pour seul code identifiant leur ensemble de sommets. Ces résultats répondent à des questions ouvertes précédemment étudiées dans la littérature.Puis, nous étudions la relation entre la taille minimum d'un code identifiant et le degré maximum d'un graphe, en particulier en donnant divers majorants pour ce paramètre en fonction de l'ordre et du degré maximum. Ces majorants sont obtenus via deux techniques. L'une est basée sur la construction d'ensembles indépendants satisfaisant certaines propriétés, et l'autre utilise la combinaison de deux outils de la méthode probabiliste : le lemme local de Lovasz et une borne de Chernoff. Nous donnons également des constructions de familles de graphes en relation avec ce type de majorants, et nous conjecturons que ces constructions sont optimales à une constante additive près.Nous présentons également de nouveaux minorants et majorants pour la cardinalité minimum d'un code identifiant dans des classes de graphes particulières. Nous étudions les graphes de maille au moins 5 et de degré minimum donné en montrant que la combinaison de ces deux paramètres influe fortement sur la taille minimum d'un code identifiant. Nous appliquons ensuite ces résultats aux graphes réguliers aléatoires. Puis, nous donnons des minorants pour la taille d'un code identifiant des graphes d'intervalles et des graphes d'intervalles unitaires. Enfin, nous donnons divers minorants et majorants pour cette quantité lorsque l'on se restreint aux graphes adjoints. Cette dernière question est abordée via la notion nouvelle de codes arête-identifiants.Pour la partie algorithmique, il est connu que le problème de décision associés à la notion de code identifiant est NP-complet même pour des classes de graphes restreintes. Nous étendons ces résultats à d'autres classes de graphes telles que celles des graphes split, des co-bipartis, des adjoints ou d'intervalles. Pour cela nous proposons des réductions polynomiales depuis divers problèmes algorithmiques classiques. Ces résultats montrent que dans beaucoup de classes de graphes, le problème des codes identifiants est algorithmiquement plus difficile que des problèms liés (tel que le problème des ensembles dominants).Par ailleurs, nous complétons les connaissances relatives à l'approximabilité du problème d'optimisation associé aux codes identifiants. Nous étendons le résultat connu de NP-difficulté pour l'approximation de ce problème avec un facteur sous-logarithmique (en fonction de la taille du graphe instance) aux graphes bipartis, split et co-bipartis, respectivement. Nous étendons également le résultat connu d'APX-complétude pour les graphes de degré maximum donné à une sous-classe des graphes split, aux graphes bipartis de degré maximum 4 et aux graphes adjoints. Enfin, nous montrons l'existence d'un algorithme de type PTAS pour les graphes d'intervalles unitaires. / An identifying code is a set of vertices of a graph such that, on the one hand, each vertex out of the code has a neighbour in the code (domination property), and, on the other hand, all vertices have a distinct neighbourhood within the code (separation property). In this thesis, we investigate combinatorial and algorithmic aspects of identifying codes.For the combinatorial part, we first study extremal questions by giving a complete characterization of all finite undirected graphs having their order minus one as minimum size of an identifying code. We also characterize finite directed graphs, infinite undirected graphs and infinite oriented graphs having their whole vertex set as unique identifying code. These results answer open questions that were previously studied in the literature.We then study the relationship between the minimum size of an identifying code and the maximum degree of a graph. In particular, we give several upper bounds for this parameter as a function of the order and the maximum degree. These bounds are obtained using two techniques. The first one consists in the construction of independent sets satisfying certain properties, and the second one is the combination of two tools from the probabilistic method: the Lovasz local lemma and a Chernoff bound. We also provide constructions of graph families related to this type of upper bounds, and we conjecture that they are optimal up to an additive constant.We also present new lower and upper bounds for the minimum cardinality of an identifying code in specific graph classes. We study graphs of girth at least 5 and of given minimum degree by showing that the combination of these two parameters has a strong influence on the minimum size of an identifying code. We apply these results to random regular graphs. Then, we give lower bounds on the size of a minimum identifying code of interval and unit interval graphs. Finally, we prove several lower and upper bounds for this parameter when considering line graphs. The latter question is tackled using the new notion of an edge-identifying code.For the algorithmic part, it is known that the decision problem associated to the notion of an identifying code is NP-complete, even for restricted graph classes. We extend the known results to other classes such as split graphs, co-bipartite graphs, line graphs or interval graphs. To this end, we propose polynomial-time reductions from several classical hard algorithmic problems. These results show that in many graph classes, the identifying code problem is computationally more difficult than related problems (such as the dominating set problem).Furthermore, we extend the knowledge of the approximability of the optimization problem associated to identifying codes. We extend the known result of NP-hardness of approximating this problem within a sub-logarithmic factor (as a function of the instance graph) to bipartite, split and co-bipartite graphs, respectively. We also extendthe known result of its APX-hardness for graphs of given maximum degree to a subclass of split graphs, bipartite graphs of maximum degree 4 and line graphs. Finally, we show the existence of a PTAS algorithm for unit interval graphs.

This thesis is devoted to the outer and grounded string representations of graphs and their subclasses. A string representation of a graph is a set of strings (bounded continuous curves in a plane), where each string corresponds to one vertex of the graph. Two strings intersect each other if and only if the two corresponding vertices are adjacent in the original graph. An outer string graph is a graph with a string representation where strings are realized inside a disk and one endpoint of each string lies on the boundary of the disk. Similarly, in case of grounded string graphs the strings lie in a common half- plane with one endpoint of each string on the boundary of the half-plane. We give a summary of subclasses of grounded string graphs and proves several results about their mutual inclusions and separations. To prove those, we use an order-forcing lemma which can be used to force a particular order of the endpoints of the string on the boundary circle or boundary line. The second part of the thesis contains proof that recognition of outer string graphs is NP-hard. 1

Un hypercube latin (LHD) maximin est un ensemble de points contenus dans un hypercube tel que les points ne partagent de coordonnées sur aucune dimension et tel que la distance minimale entre deux points est maximale. Les LHDs maximin sont particulièrement utilisés pour la construction de métamodèles en raison de leurs bonnes propriétés pour l’échantillonnage. Comme la plus grande partie des travaux concernant les LHD se sont concentrés sur leur construction par des algorithmes heuristiques, nous avons décidé de produire une étude détaillée du problème, et en particulier de sa complexité et de son approximabilité en plus des algorithmes heuristiques permettant de le résoudre en pratique.Nous avons généralisé le problème de construction d’un LHD maximin en définissant le problème de compléter un LHD entamé en respectant la contrainte maximin. Le sous-problème dans lequel le LHD partiel est vide correspond au problème de construction de LHD classique. Nous avons étudié la complexité du problème de complétion et avons prouvé qu’il est NP-complet dans de nombreux cas. N’ayant pas déterminé la complexité du sous-problème, nous avons cherché des garanties de performances pour les algorithmes résolvant les deux problèmes.D’un côté, nous avons prouvé que le problème de complétion n’est approximable pour aucune norme en dimensions k ≥ 3. Nous avons également prouvé un résultat d’inapproximabilité plus faible pour la norme L1 en dimension k = 2. D’un autre côté, nous avons proposé un algorithme d’approximation pour le problème de construction, et avons calculé le rapport d’approximation grâce à deux bornes supérieures que nous avons établies. En plus de l’aspect théorique de cette étude, nous avons travaillé sur les algorithmes heuristiques, et en particulier sur la méta-heuristique du recuit simulé. Nous avons proposé une nouvelle fonction d’évaluation pour le problème de construction et de nouvelles mutations pour les deux problèmes, permettant d’améliorer les résultats rapportés dans la littérature. / A maximin Latin Hypercube Design (LHD) is a set of point in a hypercube which do not share a coordinate on any dimension and such that the minimal distance between two points, is maximal. Maximin LHDs are widely used in metamodeling thanks to their good properties for sampling. As most work concerning LHDs focused on heuristic algorithms to produce them, we decided to make a detailed study of this problem, including its complexity, approximability, and the design of practical heuristic algorithms.We generalized the maximin LHD construction problem by defining the problem of completing a partial LHD while respecting the maximin constraint. The subproblem where the partial LHD is initially empty corresponds to the classical LHD construction problem. We studied the complexity of the completion problem and proved its NP-completeness for many cases. As we did not determine the complexity of the subproblem, we searched for performance guarantees of algorithms which may be designed for both problems. On the one hand, we found that the completion problem is inapproximable for all norms in dimensions k ≥ 3. We also gave a weaker inapproximation result for norm L1 in dimension k = 2. On the other hand, we designed an approximation algorithm for the construction problem which we proved using two new upper bounds we introduced.Besides the theoretical aspect of this study, we worked on heuristic algorithms adapted for these problems, focusing on the Simulated Annealing metaheuristic. We proposed a new evaluation function for the construction problem and new mutations for both the construction and completion problems, improving the results found in the literature.

Combinatorial optimization include such tasks as finding the quickest route to work, scheduling jobs to specialists, and placing bus stops so as to minimize commuter times. We consider problems where one is given a collection of constraints with the objective of finding an assignment satisfying as many constraints as possible, also known as Constraint Satisfaction Problems (CSPs). Most CSPs are NP-hard to solve optimally and we turn to approximations - a solution is said to be a factor-c approximation if its satisfies at least c times the optimal number of constraints. This thesis presents new results on the approximation limits of CSPs in various settings. In ordering CSPs, one is given constraints which specify the relative order of items, and the objective is order the items so as to satisfy as many constraints as possible. We give improved approximation hardness results for two classical problems: it is NP-hard to approximate Maximum Acyclic Subgraph with a factor better than 14/15 and Maximum Betweenness with a factor better than 1/2. We present ordering problems which are NP-hard to approximate better than random assignments, and that there are ordering problems arbitrarily hard to approximate. Next, Gaussian elimination can efficiently find exact solutions for satisfiable collections of so-called parity constraints. We show that whenever constraints accept at least one assignment in addition to a parity, then the problem is NP-hard to approximate better than random assignments. Finally, we study the uselessness property which basically states that if one is given a collection where almost all constraints are simultaneously satisfiable and one is permitted to relax the constraints to accept or reject additional assignments, then it is still NP-hard to find solutions noticeably better than random assignments. We consider the setting where all variables appear unnegated and provide the first examples of non-trivially useless predicates assuming only P != NP. / Kombinatoriska optimering inkluderar naturliga uppgifter såsom att hitta den snabbaste vägen till sitt arbetet, att schemalägga jobb hos specialister, eller att placera hållplatser för att minimera resenärers restid.Vi begränsar vi oss till de problem i vilket man ges en samling vilkor på variablermed målet att hitta en tilldelning av variablerna uppfyllandes så många som möjligt av vilkoren;så kallade Vilkorsuppfyllningsproblem (eng: Constraint Satisfaction Problems, CSPs).De flesta CSPs är NP-svåra att lösa optimalt och vi beaktar istället approximationer. Specifikt kallas, för 0 &lt;= c &lt;= 1, en lösning för en faktor-c approximation om antalet vilkor uppfyllda av lösningen är minst cgånger det största antalet uppfyllda av någon läsning. Denna avhandling består av tre artiklar som presenterar nya resultat begränsande hurpass väl man kan approximera CSPs i diverse situationer.För paritetsvilkor är en samling konsistenta vilkor enkla att lösa genom Gausselimination. Vi visar att för samtliga vilkor som uppfylls av en paritet och åtminstonde en ytterliggare tilldelning så är det inte bara NP-svårt at lösa utan till och med att ge en icke-trivial approximation.Oanvändarbarhet är en stark svårighetsegenskap som i princip säger att det är NP-svårt att ge icke-triviala approximationer även när man gemensamt för alla vilkor får ändra vad som uppfyller dem eller inte. Vi ger de första exemplen på icke-trivialt oanvändbara vilkor utan negationer betingat endast på P != NP.Vi visar på approximerbarhet för diverse ordningsvilorsproblem. I dessa ges man vilkor på hur objekt ska vara ordnade relativt varandra och målet är att hitta en ordning som uppfyller så många av vilkoren som möjligt. Vi ger bättre svårighetsresultat för de två mest välkända ordningsproblem, visar att det finns problem där det är NP-svårt att approximera bättre än triviala strategier, och att det finns ordningsproblem där godtyckligt dåliga approximationsgarantier är NP-svåra. / <p>NADA är en delad institution mellan SU och KTH där senare nu kallar den CSC.</p> / ApproxNP

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

NP search problems and reductions among them Renáta Ševčíková In the thesis we study the class of Total NP search problems. More attention is devoted to study the subclasses of Total NP search problems and reductions among them. We combine some known methods: the search trees and their relation to re- ductions, the Nullstellensatz refutation and the degree lower bound based on design to show that two classes of relativized NP search problems based on Mod-p counting principle and Mod-q counting principle, where p and q are different primes, are not reducible to each other. This thesis is finished by a new separation result for p = 2 and q = 3.

Neste trabalho estudamos a interação entre átomos de Rydberg no estado nP e sua dependência com o campo elétrico dc. Estes estados apresentam ressonâncias Föster para um número quântico principal n menor que 37. Nestes processos de ressonância um par atômico no estado nP muda para um par nS+(n+1)S. Realizamos dois experimentos de evolução temporal para 32&le;n&le;36. No primeiro investigamos a dependência da taxa de transferência de população NnS em função do número quântico principal n. E no segundo estudamos a transferência de população para um estado fixo de n=33 em função do campo elétrico. Além disso, estudamos a dependência da população no estado 33S em função da densidade de átomos de Rydberg no estado 33P. Estes resultados nos permitem observar duas contribuições distintas, uma linear relacionada a radiação de corpo negro e uma quadrática ligada a interação de dois corpos. Estes resultados confirmam o modelo de taxa para o efeito da radiação de corpo negro. / In this work we studied the role of Rydberg atoms interactions in the nP state and the dc electric field dependency of this process. The nP state shows Föster resonances for principal quantum number less than 37. In this resonance process, an atomic pair in nP state changes to a pair nS+(n+1)S. We have performed two time evolution experiments for 32&le;n&le;36. In the first one we have investigated the NnS population transfer rate for a variable principal quantum number n. In the second we have study the population transfer for a fixed n=33, by varying an electric field. Moreover, we observed the density dependency of the population in the 33S state by varying the nP state atomic density. The results allow us to observe two distinct contributions, a linear contribution related with the black body radiation and a quadratic one connected with two body process. The results agree well with the rate model used to treat the black body radiation.