On some classical and new hypergraph invariants
On some classical and new hypergraph invariants
复制标题
DOI：
--
复制
发表时间：
2016-12
期刊：
影响因子：
--
通讯作者：
Andrea Munaro
中科院分区：
文献类型：
--
作者：
Andrea Munaro
在本文中，我们考虑了几个超图参数，并研究了对超图子类的限制是否允许获得理想的组合或算法性质。我们考虑的大多数参数都是超图的填充和截线的特殊实例。在第一部分中，我们重点讨论了次三次无三角形图的线形图，并证明了任意这样的图G都有一个独立的集，其大小至少为3|V(G)|/10，其界是尖锐的。作为一个直接的结果，我们得到了次三次无三角形图匹配数的紧下界。此外，在次三次无三角形图的线形图上，我们证明了与反馈顶点集、哈密顿循环和哈密顿路径相关的几个算法结果。然后我们考虑三个具有Erdős-Posa属性的超图，并试图确定最优边界函数。首先，我们为亚三次图类提供了一个最优的theta-bounding function，并且我们研究了CLIQUE COVER：回答Cerioli等人的问题，我们证明了它允许平面图的PTAS。然后重点讨论了Tuza猜想，并证明了对于边最多包含四个三角形的图和通过禁止某些奇轮得到的图，可以改进该命题中的常数2。最后，我们集中讨论了琼斯猜想：我们在最大度不超过4的无爪图的情况下证明了它，并在次三次图的情况下做了一些观察。然后研究了由图产生的集合系统的vc维。特别地，我们考虑了某图的顶点集上的集合系统，它是由它的k连通子图族归纳而来的。推广Kranakis等人的结果，我们提供了vc维的紧上界和下界，并证明其计算是np完备的，对于每个k > 0。最后，我们证明了这个问题（在k = 1的情况下）和密切相关的CONNECTED支配集是np完全的或多项式时间可解的，当限制在通过禁止单个诱导子图获得的图的类别时。在论文的最后一部分，我们考虑了以下元问题：某个“难”的图问题何时变得“容易”？“简单”和“困难”实例之间是否存在“边界”？为了在遗传类的情况下回答这些问题，Alekseev引入了np困难问题的边界类的概念，并证明了当且仅当X包含Pi的边界类时，问题Pi对于有限定义的（遗传）类X是np困难的。我们继续寻找以下问题的边界类：通过指定边的哈密顿循环、哈密顿路径、反馈顶点集、连通支配集和连通顶点覆盖。
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-Posa 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.