Florian Galliot ; Sylvain Gravier ; Isabelle Sivignon - (k − 2)-linear connected components in hypergraphs of rank k

dmtcs:10202 - Discrete Mathematics & Theoretical Computer Science, November 30, 2023, vol. 25:3 special issue ICGT'22 - https://doi.org/10.46298/dmtcs.10202
(k − 2)-linear connected components in hypergraphs of rank kArticle

Authors: Florian Galliot 1,2,3,4; Sylvain Gravier ORCID1,2,3,4; Isabelle Sivignon ORCID5,2,6,3,4

We define a q-linear path in a hypergraph H as a sequence (e_1,...,e_L) of edges of H such that |e_i ∩ e_i+1 | ∈ [[1, q]] and e_i ∩ e_j = ∅ if |i − j| > 1. In this paper, we study the connected components associated to these paths when q = k − 2 where k is the rank of H. If k = 3 then q = 1 which coincides with the well-known notion of linear path or loose path. We describe the structure of the connected components, using an algorithmic proof which shows that the connected components can be computed in polynomial time. We then mention two consequences of our algorithmic result. The first one is that deciding the winner of the Maker-Breaker game on a hypergraph of rank 3 can be done in polynomial time. The second one is that tractable cases for the NP-complete problem of "Paths Avoiding Forbidden Pairs" in a graph can be deduced from the recognition of a special type of line graph of a hypergraph.


Volume: vol. 25:3 special issue ICGT'22
Section: Special issues
Published on: November 30, 2023
Accepted on: October 19, 2023
Submitted on: October 25, 2022
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]

Consultation statistics

This page has been seen 331 times.
This article's PDF has been downloaded 261 times.