On the Parameterised Complexity of Induced Multipartite Graph Parameters

Mann, RL; Mathieson, L; Greenhill, C

On the Parameterised Complexity of Induced Multipartite Graph Parameters

Mann, RL Mathieson, L

Greenhill, C

Permalink

Publication Type:: Journal Article
Citation:: 2020
Issue Date:: 2020-04-21

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download full textAdobe PDF (296.1 kB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Mann, RL
dc.contributor.author	Mathieson, L https://orcid.org/0000-0001-6470-2296
dc.contributor.author	Greenhill, C
dc.date.accessioned	2022-08-01T09:20:39Z
dc.date.available	2022-08-01T09:20:39Z
dc.date.issued	2020-04-21
dc.identifier.citation	2020
dc.identifier.uri	http://hdl.handle.net/10453/159450
dc.description.abstract	We introduce a family of graph parameters, called induced multipartite graph parameters, and study their computational complexity. First, we consider the following decision problem: an instance is an induced multipartite graph parameter $p$ and a given graph $G$, and for natural numbers $k\geq2$ and $\ell$, we must decide whether the maximum value of $p$ over all induced $k$-partite subgraphs of $G$ is at most $\ell$. We prove that this problem is W[1]-hard. Next, we consider a variant of this problem, where we must decide whether the given graph $G$ contains a sufficiently large induced $k$-partite subgraph $H$ such that $p(H)\leq\ell$. We show that for certain parameters this problem is para-NP-hard, while for others it is fixed-parameter tractable.
dc.language	en
dc.rights	info:eu-repo/semantics/openAccess
dc.title	On the Parameterised Complexity of Induced Multipartite Graph Parameters
dc.type	Journal Article
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	open_access	*
dc.date.updated	2022-08-01T09:20:37Z

Abstract:

We introduce a family of graph parameters, called induced multipartite graph parameters, and study their computational complexity. First, we consider the following decision problem: an instance is an induced multipartite graph parameter $p$ and a given graph $G$, and for natural numbers $k\geq2$ and $\ell$, we must decide whether the maximum value of $p$ over all induced $k$-partite subgraphs of $G$ is at most $\ell$. We prove that this problem is W[1]-hard. Next, we consider a variant of this problem, where we must decide whether the given graph $G$ contains a sufficiently large induced $k$-partite subgraph $H$ such that $p(H)\leq\ell$. We show that for certain parameters this problem is para-NP-hard, while for others it is fixed-parameter tractable.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/159450