VC次元は、セットシステム（またはハイパーグラフ）の複雑性を測る基本的かつ広く研究されている尺度で、機械学習の多くの分野において中心的な役割を果たします。本研究では、VC次元の計算に関する複雑性の新しい結果をいくつか確立しました。特に、ハイパーグラフ \mathcal{H}=(\mathcal{V},\mathcal{E}) に対して、単純な 2^{\mathcal{O}(|\mathcal{V}|)} 時間アルゴリズムが指数時間仮説（ETH）の下で漸近的に厳密であることを証明しました。さらに、最大次数や次元によってパラメータ化された場合に、1-additive固定パラメータ近似アルゴリズムが存在することを証明し、これらが基本的な構造パラメータであることを示しています。最後に、グラフを用いた問題の一般化を考慮し、ツリ幅によってパラメータ化された場合に固定パラメータ的に扱えることを示しました。このアルゴリズムは、ツリ幅に対する依存度が比較的低いことが特徴です。