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.