We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Integer programming formulations for the k$k$‐in‐a‐tree problem in graphs.
- Authors
Ferreira, Lucas Saldanha; Santos, Vinicius Fernandes dos; Valle, Cristiano Arbex
- Abstract
Chudnovsky and Seymour proposed the Three‐in‐a‐tree algorithm which solves the following problem in polynomial time: given three fixed vertices in a simple finite graph, check whether an induced tree containing these vertices exists. In this paper, we deal with a generalization of this problem, referred to henceforth as k$k$‐in‐a‐tree. The k$k$‐in‐a‐tree checks whether a graph contains an induced tree spanning k$k$ given vertices. When k$k$ is part of the input, the problem is known to be NP‐complete. If k≥4$k \ge 4$ is a fixed given number, its complexity is an open question, although there are efficient algorithms for restricted cases such as claw‐free graphs, graphs with a girth of at least k$k$ and chordal graphs. We present mixed‐integer programming formulations for this problem, and we show that instances with up to 25,000 vertices can be solved in reasonable computational time.
- Subjects
INTEGER programming; POLYNOMIAL time algorithms; SPANNING trees; PROBLEM solving; OPEN-ended questions
- Publication
International Transactions in Operational Research, 2024, Vol 31, Issue 5, p3090
- ISSN
0969-6016
- Publication type
Article
- DOI
10.1111/itor.13297