## 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.

**Definition 1 (Induced multipartite graph parameter)**A graph parameter \(p\) is an

*induced multipartite graph parameter*if the following properties are satisfied.

- 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.

**Induced \(k\)-Partite Subgraph Parameter**

- 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.

**Theorem 1**Induced \(k\)-Partite Subgraph Parameter is \(\text{W[1]-hard}\) for any induced multipartite graph parameter.

We then study the following variant of the problem.

**Large Induced \(k\)-Partite Subgraph Parameter**

- 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.

**Theorem 2**Large Induced \(k\)-Partite Subgraph Parameter is \(\text{para-NP-hard}\) for the following induced multipartite graph parameters: maximum degree, minimum degree, vertex connectivity, edge connectivity, and chromatic index.

**Theorem 3**Large Induced \(k\)-Partite Subgraph Parameter is fixed-parameter tractable for the following induced multipartite graph parameters: number of vertices and number of edges.