Counting $P_3$-convex sets in graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910041645252608 |
|---|---|
| author | Dourado, Mitre C. Grippo, Luciano N. Lin, Min Chih Protti, Fábio |
| author_facet | Dourado, Mitre C. Grippo, Luciano N. Lin, Min Chih Protti, Fábio |
| contents | We study the $P_3$-convexity, the path convexity generated by all three-vertex paths, and focus on the problem of counting the $P_3$-convex vertex sets of a graph $G$, denoted by $\noc(G)$. First, we settle the associated extremal question: we characterize the $n$-vertex graphs maximizing $\noc(G)$ among all graphs and determine the connected extremal graphs. Next, we investigate computational complexity and show that counting $P_3$-convex sets is $\#\mathsf{P}$-complete already on split graphs, even under additional structural restrictions. On the positive side, we identify two tractable subclasses, namely trees and threshold graphs, and obtain linear-time algorithms for both. Finally, we design nontrivial exact exponential-time algorithms for general graphs, combining structural decomposition, propagation rules capturing forced consequences of $P_3$-convexity, and fast counting of independent sets in auxiliary graphs. The resulting strategy becomes particularly effective on graph classes where large independent sets are guaranteed and can be found efficiently. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_04706 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Counting $P_3$-convex sets in graphs Dourado, Mitre C. Grippo, Luciano N. Lin, Min Chih Protti, Fábio Combinatorics G.2.2; G.2.1 We study the $P_3$-convexity, the path convexity generated by all three-vertex paths, and focus on the problem of counting the $P_3$-convex vertex sets of a graph $G$, denoted by $\noc(G)$. First, we settle the associated extremal question: we characterize the $n$-vertex graphs maximizing $\noc(G)$ among all graphs and determine the connected extremal graphs. Next, we investigate computational complexity and show that counting $P_3$-convex sets is $\#\mathsf{P}$-complete already on split graphs, even under additional structural restrictions. On the positive side, we identify two tractable subclasses, namely trees and threshold graphs, and obtain linear-time algorithms for both. Finally, we design nontrivial exact exponential-time algorithms for general graphs, combining structural decomposition, propagation rules capturing forced consequences of $P_3$-convexity, and fast counting of independent sets in auxiliary graphs. The resulting strategy becomes particularly effective on graph classes where large independent sets are guaranteed and can be found efficiently. |
| title | Counting $P_3$-convex sets in graphs |
| topic | Combinatorics G.2.2; G.2.1 |
| url | https://arxiv.org/abs/2603.04706 |