English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  b-Coloring Parameterized by Pathwidth is XNLP-complete

Jaffke, L., Lima, P. T., & Sharma, R. (2022). b-Coloring Parameterized by Pathwidth is XNLP-complete. Retrieved from https://arxiv.org/abs/2209.07772.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/21.11116/0000-000C-1E7E-7 Version Permalink: https://hdl.handle.net/21.11116/0000-000C-1E7F-6
Genre: Paper
Latex : $b$-Coloring Parameterized by Pathwidth is {XNLP}-complete

Files

show Files
hide Files
:
arXiv:2209.07772.pdf (Preprint), 433KB
View   Save
File Permalink:
https://hdl.handle.net/21.11116/0000-000C-1E80-2
Name:
arXiv:2209.07772.pdf
Description:
File downloaded from arXiv at 2023-01-04 10:04
OA-Status:
Green
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
View
Copyright Date:
-
Copyright Info:
-
License:
http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Locators

show

Creators

show
hide
 Creators:
Jaffke, Lars1, Author
Lima, Paloma T.1, Author
Sharma, Roohani2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS
 Abstract: We show that the $b$-Coloring problem is complete for the class XNLP when
parameterized by the pathwidth of the input graph. Besides determining the
precise parameterized complexity of this problem, this implies that b-Coloring
parameterized by pathwidth is $W[t]$-hard for all $t$, and resolves the
parameterized complexity of $b$-Coloring parameterized by treewidth.

Details

show
hide
Language(s): eng - English
 Dates: 2022-09-162022
 Publication Status: Published online
 Pages: 7 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 2209.07772
BibTex Citekey: Jaffke2209.07772
URI: https://arxiv.org/abs/2209.07772
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show