# Ryan Mann

Quantum Physics, Complexity Theory, & Combinatorics

## On the Parameterised Complexity of Induced Multipartite Graph Parameters

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.
1. If $$H$$ is an induced subgraph of $$K_{n|k}$$ then $$p(H) \leq p(K_{n|k})$$.
2. 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)$$.
For a given induced multipartite graph parameter $$p$$, let $$p(G,k)$$ be the maximum value of $$p(H)$$ over all induced $$k$$-partite subgraphs $$H$$ of $$G$$.

This family includes a number of well-studied graph parameters, including vertex and edge connectivity, independence number, 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: independence number, treewidth, pathwidth, number of vertices, and number of edges.