Skip to content

Motivation

Routing and Wavelength Assignment (RWA)

Problem (RWA):

In WDM networks, given a set of traffic requests and a (directed) network, assign a route and a wavelength to each request such that no two routes sharing a fiber use the same wavelength.

  • Goal: minimize the number of wavelengths used.
  • The problem is NP-hard.

Classical two‑step approach

  1. Find the routes (dipaths).
  2. Assign wavelengths = colouring of a conflict graph: vertices are dipaths, wavelengths are colours, an edge connects two dipaths if they share a fiber.

This reduces to graph colouring, which is NP-hard [Karp, 1972].

UPP‑DAG: A directed acyclic graph with the unique dipath property (at most one dipath between any two vertices).

  • In a UPP‑DAG the routing is forced.
  • Load: maximum number of paths sharing a fiber.
  • Hope: the number of required wavelengths can be bounded by a function of the load.

Key observation [Bermond, Cosnard, Pérennes 2013]:

  • The conflict graph of a set of dipaths of load 2 in a UPP‑DAG admits a good edge‑labeling.
  • Conversely, every graph with a good edge‑labeling is the conflict graph of a set of dipaths of load 2 in some UPP‑DAG.

Thus studying good edge‑labelings is directly motivated by RWA with load 2.

Good Edge‑Labelings

Definition. An edge‑labeling of a graph \(G\) is a function \(\phi: E(G) \to \mathbb{R}\).
A path is increasing if the sequence of its edge labels is non‑decreasing.

An edge‑labeling is good if for any two distinct vertices \(u, v\), there is at most one increasing \((u,v)\)-path.

Problem (\(\mathsf{GEL}\)): Given a graph \(G\), does \(G\) admit a good edge‑labeling?

Basic remarks:

  • \(G\) is good under some labeling iff it is good under an injective integer labeling.
  • \(G\) is good iff it does not contain two internally disjoint increasing paths between any pair of vertices.

Examples of good and bad graphs:

  • \(C_3\) and \(K_{2,3}\) are bad (no good labeling possible).
  • Not every \(\{C_3,K_{2,3}\}\)-free graph is good; there exist infinite families of bad graphs without these subgraphs (e.g., the graph \(H_k\), and a newer example on 9 vertices).

Critical Graphs and Structural Properties

A graph is critical if it is bad but every proper subgraph is good.
Lemma [Araújo et al. 2012]:

  • A critical graph has no matching cut.
  • A critical graph has no cut‑vertex.

A matching cut is an edge cut that is a matching, and a cut‑vertex is a vertex whose removal disconnects the graph.

These properties are heavily used in reduction rules.

Complexity of Deciding Good Edge‑Labelings

Theorem [Araújo et al. 2012]: Deciding whether a bipartite graph is good is \(\mathsf{NP}\)‑complete.

Classes of graphs that are known to be good:

  • \(C_3\)-free outerplanar graphs,
  • \(\{C_3,K_{2,3}\}\)-free subcubic graphs,
  • graphs with \(|E(G)| < \frac{3}{2}(|V(G)|-1)\).

The key idea behind these results is the absence of matching cuts.

Density and Extremal Results

Mehrabian (2012):

  • Every good graph on \(n\) vertices with maximum degree within a constant factor of its average degree has at most \(n^{1+o(1)}\) edges.
  • There exist bad graphs with arbitrarily large girth.
  • For any \(\Delta\) there exists a \(g\) such that every graph with maximum degree \(\le \Delta\) and girth \(\ge g\) is good.

Mehrabian, Mitsche, Pralat (2013):

  • Any good graph on \(n\) vertices has at most \(\frac12 n \log_2 n\) edges, and this bound is tight for infinitely many \(n\).

Connection to temporal graphs:

An edge‑labeled graph is a temporal graph; an increasing path is a temporal path. A good edge‑labeling corresponds to a temporization with low “temporal connectivity”.

The \(c\)-GEL Variant

For an integer \(c \ge 1\), a \(c\)-edge‑labeling uses at most \(c\) distinct labels. A graph admits a good \(c\)-edge‑labeling (abbreviated \(c\)-gel) if it is good and the labeling only requires \(c\) different values.

  • \(c\)-good: admits a \(c\)-gel; otherwise \(c\)-bad.

Problem (\(c\)-GEL):

Input: a graph \(G\).

Question: does \(G\) admit a \(c\)-gel?

Example: The graph shown on slide 17 admits a \(3\)-gel.
A special property for \(c=2\): certain edges must receive the same label (slide 18).

Main Contributions (de Andrade, Araújo, Morelle, Sau, Silva 2024)

Classical complexity:

  • \(c\)-GEL is in NP for every \(c \ge 2\).
  • \(c\)-GEL is NP‑hard for every \(c \ge 2\), even on bipartite bounded‑degree graphs that admit a \((c+1)\)-gel.
    • Reduction from Not‑All‑Equal 3‑SAT (NAE 3‑SAT).
    • Gadgets: variable gadget \(X_i\), clause gadget \(C_j\), path gadget \(P_{i,j,a}\); for general \(c\), an extremal gadget \(X\) and a \(c\)‑color gadget \(D_c\).

Parameterized complexity:

  • Kernelization:
    • Linear kernel for parameter neighborhood diversity \(nd(G)\).
    • Quadratic kernel for parameter vertex cover number \(vc(G)\).
    • Reduction rules exploit \(K_3\), \(K_{2,3}\), cut‑vertices, and matching cuts.
  • FPT algorithms:
    • \({\sf GEL}\) is FPT parameterized by star‑forest modulator \(sfm\) (size of a modulator to a star forest).
    • \(c\)‑\({\sf GEL}\) is FPT parameterized by \(tw + c\):
      • Can be derived via Courcelle’s Theorem.
      • Explicit dynamic programming running in time \(c^{O(tw^2)} \cdot n\) on \(n\)‑vertex graphs.
    • \({\sf GEL}\) is FPT parameterized by \(tw + \Delta\) (treewidth + maximum degree):
      • Time \(2^{O(tw\Delta^2 + tw^2 \log \Delta)} \cdot n\), and it can minimize the number of used labels.
  • Hardness of orientation: Deciding whether an undirected graph admits an orientation that is a UPP‑DAG is NP‑complete.

Kernelization Details

Definition (kernelization): A parameterized problem \(L \subseteq \Sigma^* \times \mathbb{N}\) admits a kernel of size \(g(k)\) if there is a polynomial‑time algorithm that maps \((x,k)\) to an equivalent instance \((x',k')\) with \(|x'|, k' \le g(k)\).

Linear / quadratic kernel: \(g(k) = O(k)\) / \(O(k^2)\).

Reduction rules (applied to \(G\)):

  1. If \(G\) contains \(K_3\) or \(K_{2,3}\) as a subgraph → output a trivial no‑instance.
  2. If \(G\) is disconnected, solve each connected component independently.
  3. Cut‑vertex rule: Let \(v\) be a cut‑vertex and \(C\) the vertices of a connected component of \(G \setminus v\). If \(G[C \cup \{v\}]\) is good (or \(c\)-good for \(c\)-GEL), then delete \(C\) from \(G\).
  4. Matching cut rule (only for \({\sf GEL}\)): If \(G\) has a matching cut \(S\), consider each connected component of \(G - S\) separately.

Linear kernel for neighborhood diversity \(nd(G)\):

  • \(nd(G)\) = minimum number of parts in a partition of \(V(G)\) where vertices in the same part have the same type (\(N(u)\setminus\{v\} = N(v)\setminus\{u\}\)).
  • Can be computed in cubic time [Lampis 2012].
  • After applying reduction rules, each part can be proved to be small, giving a kernel of size \(O(nd(G))\).

Quadratic kernel for vertex cover \(vc(G)\):

  • Note that \(nd(G) \le 2^{vc(G)} + vc(G)\).
  • Using a \(2\)‑approximation for vertex cover, obtain a cover \(S\) with \(|S| \le 2 \cdot vc(G)\).
  • After applying rules, there are no degree‑1 vertices, and at most \(2 \cdot \binom{2k}{2}\) vertices in \(S\) have degree at least 2. This yields a kernel with \(O(vc(G)^2)\) vertices.

Open Problems and Further Research

Current parameter landscape (bounds between parameters):

\[ tw(G)-1 \; \le \; fvs(G) \; \le \; sfm(G) \; \le \; vc(G) \]

where \(fvs\) = feedback vertex set, \(sfm\) = star‑forest modulator, \(vc\) = vertex cover.

Also \(nd(G) \le 2^{vc(G)} + vc(G)\), but \(nd\) is incomparable with \(tw\), \(fvs\), \(sfm\).

Open questions:

  • Is \(\mathsf{GEL\ FPT}\) parameterized by \(fvs\) or by \(tw\) alone? Is it in XP for these parameters?
  • Does there exist a function \(f\) such that every good graph is \(f(tw)\)-good? (i.e., the number of labels needed for a good labeling can be bounded by a function of the treewidth)
  • Analogously, does there exist a function \(f\) such that every good graph is \(f(\Delta)\)-good? (labels bounded by a function of the maximum degree)