The hardness of embedding grids and walls
International Workshop on Graph-Theoretic Concepts in Computer Science, 2017•Springer
The dichotomy conjecture for the parameterized embedding problem states that the problem
of deciding whether a given graph G from some class\mathcal KK of “pattern graphs” can be
embedded into a given graph H (that is, is isomorphic to a subgraph of H) is fixed-parameter
tractable if\mathcal KK is a class of graphs of bounded tree width and W 1 W 1-complete
otherwise. Towards this conjecture, we prove that the embedding problem is W 1 W 1-
complete if\mathcal KK is the class of all grids or the class of all walls.
of deciding whether a given graph G from some class\mathcal KK of “pattern graphs” can be
embedded into a given graph H (that is, is isomorphic to a subgraph of H) is fixed-parameter
tractable if\mathcal KK is a class of graphs of bounded tree width and W 1 W 1-complete
otherwise. Towards this conjecture, we prove that the embedding problem is W 1 W 1-
complete if\mathcal KK is the class of all grids or the class of all walls.
Abstract
The dichotomy conjecture for the parameterized embedding problem states that the problem of deciding whether a given graph G from some class of “pattern graphs” can be embedded into a given graph H (that is, is isomorphic to a subgraph of H) is fixed-parameter tractable if is a class of graphs of bounded tree width and -complete otherwise.
Towards this conjecture, we prove that the embedding problem is -complete if is the class of all grids or the class of all walls.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果