On the Parameterised Complexity of Induced Multipartite Graph Parameters
April 22, 2020
Luke Mathieson, Catherine Greenhill, and I have just uploaded to arXiv our paper "On the Parameterised Complexity of Induced Multipartite Graph Parameters". In this paper we introduce a family of graph parameters, called induced multipartite graph parameters, and study their computational complexity.
- If \(H\) is a subgraph of \(K_{n|k}\) then \(p(H) \leq p(K_{n|k})\).
- For each \(k\geq2\) there is an efficiently computable injective function \(f_k:\mathbb{Z}^+\to\mathbb{N}\) such that \(p(K_{n|k})=f_k(n)\).
This family includes a number of well-studied graph parameters, including vertex and edge connectivity, chromatic index, treewidth, and pathwidth. We first study the complexity of the following problem.
- Instance:
- A graph \(G\).
- Parameter:
- Natural numbers \(k\geq2\) and \(\ell\).
- Problem:
- Decide whether \(p(G,k)\) is at most \(\ell\).
We show that this problem is \(\text{W[1]-hard}\) in general.
We then study the following variant of the problem.
- Instance:
- A graph \(G\).
- Parameter:
- Natural numbers \(k\geq2\), \(\ell\), and \(m\).
- Problem:
- Decide whether there is an induced \(k\)-partite subgraph \(H\) of \(G\) such that \(p(H)\leq\ell\) and \(|V(H)|\geq|V(G)|-m\).
We show that the complexity of this problem depends highly on the specific induced multipartite graph parameter. This is demonstrated by the following two theorems.