Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2603.27424 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913023863554048 |
|---|---|
| author | Jiang, Yiyang Chen, Xudong |
| author_facet | Jiang, Yiyang Chen, Xudong |
| contents | In this paper, we focus on the class of complete $S$-partite graphs, for $S$ an undirected graph possibly with self-loops, and address the problem of finding largest $2$-regular subgraphs of these graphs, which can be formulated as an integer linear program. Roughly speaking, a complete $S$-partite graph is obtained by replacing every single node of $S$ with a number of nodes, preserving the edge/non-edge relations of $S$. Our motivation in finding largest $2$-regular subgraphs is rooted in the structural systems theory, particularly in the problem of finding largest subnetworks that can sustain controllability or asymptotic stability of the corresponding subsystems. A main contribution of the paper is to show that the integer linear problem can be solved efficiently in $O(|V(S)|^3)$, independent of the order/size of the $S$-partite graph itself. Furthermore, we demonstrate through simulations that with high probability, a random $S$-partite graph contains a largest $2$-regular subgraph of the same order as its complete counterpart does. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_27424 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Largest $2$-regular Subgraphs in complete $S$-partite Graphs Jiang, Yiyang Chen, Xudong Combinatorics In this paper, we focus on the class of complete $S$-partite graphs, for $S$ an undirected graph possibly with self-loops, and address the problem of finding largest $2$-regular subgraphs of these graphs, which can be formulated as an integer linear program. Roughly speaking, a complete $S$-partite graph is obtained by replacing every single node of $S$ with a number of nodes, preserving the edge/non-edge relations of $S$. Our motivation in finding largest $2$-regular subgraphs is rooted in the structural systems theory, particularly in the problem of finding largest subnetworks that can sustain controllability or asymptotic stability of the corresponding subsystems. A main contribution of the paper is to show that the integer linear problem can be solved efficiently in $O(|V(S)|^3)$, independent of the order/size of the $S$-partite graph itself. Furthermore, we demonstrate through simulations that with high probability, a random $S$-partite graph contains a largest $2$-regular subgraph of the same order as its complete counterpart does. |
| title | Largest $2$-regular Subgraphs in complete $S$-partite Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.27424 |