Families of tractable problems with respect to vertex-interval-membership width and its generalisations
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908994584444928 |
|---|---|
| author | Enright, Jessica Hand, Samuel D. Larios-Jones, Laura Meeks, Kitty |
| author_facet | Enright, Jessica Hand, Samuel D. Larios-Jones, Laura Meeks, Kitty |
| contents | Temporal graphs are graphs whose edges are labelled with times at which they are active. Their time-sensitivity provides a useful model of real networks, but renders many problems studied on temporal graphs more computationally complex than their static counterparts. To contend with this, there has been recent work devising parameters for which temporal problems become tractable. One such parameter is vertex-interval-membership (VIM) width. Broadly, this gives a bound on the number of vertices we need to keep track of at any given time to solve many problems. Our contributions are two-fold. Firstly, we introduce a new parameter, tree-interval-membership (TIM) width, that generalises both VIM width and several existing generalisations. Secondly, we provide meta-algorithms for both VIM and TIM width which can be used to prove fixed-parameter-tractability for large families of problems, bypassing the need to give involved dynamic programming arguments for every problem. In doing this, we provide a characterisation of problems in FPT with respect to both parameters. We apply these algorithms to temporal versions of Hamiltonian path, dominating set, matching, and edge deletion to limit maximum reachability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_15699 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Families of tractable problems with respect to vertex-interval-membership width and its generalisations Enright, Jessica Hand, Samuel D. Larios-Jones, Laura Meeks, Kitty Discrete Mathematics Combinatorics Temporal graphs are graphs whose edges are labelled with times at which they are active. Their time-sensitivity provides a useful model of real networks, but renders many problems studied on temporal graphs more computationally complex than their static counterparts. To contend with this, there has been recent work devising parameters for which temporal problems become tractable. One such parameter is vertex-interval-membership (VIM) width. Broadly, this gives a bound on the number of vertices we need to keep track of at any given time to solve many problems. Our contributions are two-fold. Firstly, we introduce a new parameter, tree-interval-membership (TIM) width, that generalises both VIM width and several existing generalisations. Secondly, we provide meta-algorithms for both VIM and TIM width which can be used to prove fixed-parameter-tractability for large families of problems, bypassing the need to give involved dynamic programming arguments for every problem. In doing this, we provide a characterisation of problems in FPT with respect to both parameters. We apply these algorithms to temporal versions of Hamiltonian path, dominating set, matching, and edge deletion to limit maximum reachability. |
| title | Families of tractable problems with respect to vertex-interval-membership width and its generalisations |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2505.15699 |