Three problems on well-partitioned chordal graphs
Journal article, Peer reviewed
Accepted version
Permanent lenke
https://hdl.handle.net/11250/2787349Utgivelsesdato
2021Metadata
Vis full innførselSamlinger
- Department of Informatics [917]
- Registrations from Cristin [9489]
Originalversjon
Lecture Notes in Computer Science (LNCS). 2021, 12701, 23-36. 10.1007/978-3-030-75242-2_2Sammendrag
In this work, we solve three problems on well-partitioned chordal graphs. First, we show that every connected (resp., 2-connected) well-partitioned chordal graph has a vertex that intersects all longest paths (resp., longest cycles). It is an open problem [Balister et al., Comb. Probab. Comput. 2004] whether the same holds for chordal graphs. Similarly, we show that every connected well-partitioned chordal graph admits a (polynomial-time constructible) tree 3-spanner, while the complexity status of the Tree 3-Spanner problem remains open on chordal graphs [Brandstädt et al., Theor. Comput. Sci. 2004]. Finally, we show that the problem of finding a minimum-size geodetic set is polynomial-time solvable on well-partitioned chordal graphs. This is the first example of a problem that is NP -hard on chordal graphs and polynomial-time solvable on well-partitioned chordal graphs. Altogether, these results reinforce the significance of this recently defined graph class as a tool to tackle problems that are hard or unsolved on chordal graphs.