The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909171606093824 |
|---|---|
| author | Beisegel, Jesse Chiarelli, Nina Köhler, Ekkehard Milanič, Martin Muršič, Peter Scheffler, Robert |
| author_facet | Beisegel, Jesse Chiarelli, Nina Köhler, Ekkehard Milanič, Martin Muršič, Peter Scheffler, Robert |
| contents | We propose a novel way of generalizing the class of interval graphs, via a graph width parameter called the simultaneous interval number. This parameter is related to the simultaneous representation problem for interval graphs and defined as the smallest number $d$ of labels such that the graph admits a $d$-simultaneous interval representation, that is, an assignment of intervals and label sets to the vertices such that two vertices are adjacent if and only if the corresponding intervals, as well as their label sets, intersect. We show that this parameter is $\mathsf{NP}$-hard to compute and give several bounds for the parameter, showing in particular that it is sandwiched between pathwidth and linear mim-width. For classes of graphs with bounded parameter values, assuming that the graph is equipped with a simultaneous interval representation with a constant number of labels, we give $\mathsf{FPT}$ algorithms for the clique, independent set, and dominating set problems, and hardness results for the independent dominating set and coloring problems. The $\mathsf{FPT}$ results for independent set and dominating set are for the simultaneous interval number plus solution size. In contrast, both problems are known to be $\mathsf{W}[1]$-hard for linear mim-width plus solution size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_10670 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs Beisegel, Jesse Chiarelli, Nina Köhler, Ekkehard Milanič, Martin Muršič, Peter Scheffler, Robert Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics We propose a novel way of generalizing the class of interval graphs, via a graph width parameter called the simultaneous interval number. This parameter is related to the simultaneous representation problem for interval graphs and defined as the smallest number $d$ of labels such that the graph admits a $d$-simultaneous interval representation, that is, an assignment of intervals and label sets to the vertices such that two vertices are adjacent if and only if the corresponding intervals, as well as their label sets, intersect. We show that this parameter is $\mathsf{NP}$-hard to compute and give several bounds for the parameter, showing in particular that it is sandwiched between pathwidth and linear mim-width. For classes of graphs with bounded parameter values, assuming that the graph is equipped with a simultaneous interval representation with a constant number of labels, we give $\mathsf{FPT}$ algorithms for the clique, independent set, and dominating set problems, and hardness results for the independent dominating set and coloring problems. The $\mathsf{FPT}$ results for independent set and dominating set are for the simultaneous interval number plus solution size. In contrast, both problems are known to be $\mathsf{W}[1]$-hard for linear mim-width plus solution size. |
| title | The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs |
| topic | Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2404.10670 |