Scholarlink

We study the switching graph problem (SGP) on a directed bipartite graph \(S=(I \cup J, A)\) . Every node \(j \in J\) has a switch. When we turn on the switch on j, all arcs incident to j are reversed. SGP is to find a subset \(J' \subseteq J\) which maximizes the number of nodes in I, each of which has only outgoing or incoming arcs, when all the switches on \(J'\) are turned on. SGP is NP-hard even when the maximum degree of I is 4 and studied for the constrained via minimization problem in VLSI design. Even though heuristic algorithms for SGP are studied, there are no exact or approximation algorithms. In this note, we show that SGP is reduced to the independent set problem (ISP). From this reduction and known algorithms for ISP, we give exact and approximation algorithms for SGP.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On Reduction of the Switching Graph Problem to the Independent Set Problem

  • 章节

  • 发表日期：

    2026年

查看全文
  • Yotaro Takazawa,
  • Shinji Mizuno

摘要

We study the switching graph problem (SGP) on a directed bipartite graph \(S=(I \cup J, A)\) . Every node \(j \in J\) has a switch. When we turn on the switch on j, all arcs incident to j are reversed. SGP is to find a subset \(J' \subseteq J\) which maximizes the number of nodes in I, each of which has only outgoing or incoming arcs, when all the switches on \(J'\) are turned on. SGP is NP-hard even when the maximum degree of I is 4 and studied for the constrained via minimization problem in VLSI design. Even though heuristic algorithms for SGP are studied, there are no exact or approximation algorithms. In this note, we show that SGP is reduced to the independent set problem (ISP). From this reduction and known algorithms for ISP, we give exact and approximation algorithms for SGP.