Auteur : Andréa MUNARO
Directeur de thèse : Andras SEBO
Co Directeur : Matej Stehlik
Date : 1 décembre 2016
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. Nous
continuons 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.
Directeur de thèse : Andras SEBO
Co Directeur : Matej Stehlik
Date : 1 décembre 2016
Sur quelques invariants classiques et nouveaux des hypergraphes
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. Nous
continuons 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.