We study the following general disjoint paths problem: given a supply graph G, a set T ⊆ V(G) of terminals, a demand graph H on the vertices T, and an integer k, the task is to find a set of k pairwise vertex-disjoint valid paths, where we say that a path of the supply graph G is valid if its endpoints are in T and adjacent in the demand graph H. For a class H of graphs, we denote by Maximum Disjoint ℋ-Paths the restriction of this problem when the demand graph H is assumed to be a member of ℋ. We study the fixed-parameter tractability of this family of problems, parameterized by k. Our main result is a complete characterization of the fixed-parameter tractable cases of Maximum Disjoint ℋ-Paths for every hereditary class ℋ of graphs: it turns out that complexity depends on the existence of large induced matchings and large induced skew bicliques in the demand graph H (a skew biclique is a bipartite graph on vertices a1, …, an, b1, …, bn with ai and bj being adjacent if and only if i ≤ j). Specifically, we prove the following classification for every hereditary class ℋ. If ℋ does not contain every matching and does not contain every skew biclique, then MAXIMUM Disjoint ℋ-Paths is FPT. If ℋ does not contain every matching, but contains every skew biclique, then MAXIMUM DISJOINT ℋ-Paths is W[1]-hard, admits an FPT approximation, and the valid paths satisfy an analog of the Erdös-Pósa property. If ℋ contains every matching, then MAXIMUM DISJOINT ℋ-Paths is W[1]-hard and the valid paths do not satisfy the analog of the Erdös-Pósa property.

An exact characterization of tractable demand patterns for maximum disjoint path problems / Marx, Dániel; Wollan, PAUL JOSEPH. - STAMPA. - (2015), pp. 642-661. (Intervento presentato al convegno Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) tenutosi a San Diego, CA, USA nel January 4-6, 2015) [10.1137/1.9781611973730.44].

An exact characterization of tractable demand patterns for maximum disjoint path problems

WOLLAN, PAUL JOSEPH
2015

Abstract

We study the following general disjoint paths problem: given a supply graph G, a set T ⊆ V(G) of terminals, a demand graph H on the vertices T, and an integer k, the task is to find a set of k pairwise vertex-disjoint valid paths, where we say that a path of the supply graph G is valid if its endpoints are in T and adjacent in the demand graph H. For a class H of graphs, we denote by Maximum Disjoint ℋ-Paths the restriction of this problem when the demand graph H is assumed to be a member of ℋ. We study the fixed-parameter tractability of this family of problems, parameterized by k. Our main result is a complete characterization of the fixed-parameter tractable cases of Maximum Disjoint ℋ-Paths for every hereditary class ℋ of graphs: it turns out that complexity depends on the existence of large induced matchings and large induced skew bicliques in the demand graph H (a skew biclique is a bipartite graph on vertices a1, …, an, b1, …, bn with ai and bj being adjacent if and only if i ≤ j). Specifically, we prove the following classification for every hereditary class ℋ. If ℋ does not contain every matching and does not contain every skew biclique, then MAXIMUM Disjoint ℋ-Paths is FPT. If ℋ does not contain every matching, but contains every skew biclique, then MAXIMUM DISJOINT ℋ-Paths is W[1]-hard, admits an FPT approximation, and the valid paths satisfy an analog of the Erdös-Pósa property. If ℋ contains every matching, then MAXIMUM DISJOINT ℋ-Paths is W[1]-hard and the valid paths do not satisfy the analog of the Erdös-Pósa property.
2015
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
paths problem
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
An exact characterization of tractable demand patterns for maximum disjoint path problems / Marx, Dániel; Wollan, PAUL JOSEPH. - STAMPA. - (2015), pp. 642-661. (Intervento presentato al convegno Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) tenutosi a San Diego, CA, USA nel January 4-6, 2015) [10.1137/1.9781611973730.44].
File allegati a questo prodotto
File Dimensione Formato  
Wollan_exact_2015.pdf

solo utenti autorizzati

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 510.99 kB
Formato Adobe PDF
510.99 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/796507
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact