Colored Constrained Spanning Trees on Directed Graphs
- 講者韓永楷 教授 (國立清華大學電機資訊學院資訊工程學系)
邀請人：蔡孟宗 - 時間2023-08-08 (Tue.) 10:00 ~ 12:00
- 地點資訊所新館106演講廳
摘要
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.