Colored Constrained Spanning Trees on Directed Graphs
- LecturerProf. Wing-Kai Hon (Dept. of Information Engineering, School of Electrical and Computer Engineering, National Tsing Hua University)
Host: Meng-Tsung, Tsai - Time2023-08-08 (Tue.) 10:00 ~ 12:00
- LocationAuditorium 106 at IIS new Building
Abstract
We study the Colored Constrained Spanning Tree problem on edge-colored directed graphs.
This problem targets to find a spanning tree such that for each vertex, the number of incident edges that share any specific color is bounded by some constant K.
We show that if the edges in the DAG are limited to use 2 colors and K is restricted to $1$, the problem can be solved via dynamic programming.
However, if the input graph is a general directed graph with at least 2 colors, or if it is a DAG with at least 3 colors, then the problem becomes NP-hard, for any K >= 1.
This problem targets to find a spanning tree such that for each vertex, the number of incident edges that share any specific color is bounded by some constant K.
We show that if the edges in the DAG are limited to use 2 colors and K is restricted to $1$, the problem can be solved via dynamic programming.
However, if the input graph is a general directed graph with at least 2 colors, or if it is a DAG with at least 3 colors, then the problem becomes NP-hard, for any K >= 1.