Elements of dynamic and 2-SAT programming: paths, trees, and cuts
This thesis presents faster (in terms of worst-case running times) exact algorithms for special cases of graph problems through dynamic programming and 2-SAT programming. Dynamic programming describes the procedure of breaking down a problem recursively into overlapping subproblems, that is, subprob...
Saved in:
| 主要作者: | |
|---|---|
| 格式: | Online |
| 語言: | 英语 |
| 出版: |
Universitätsverlag der Technischen Universität Berlin
2022
|
| 主題: | |
| 在線閱讀: | ONIX_20220415_9783798332096_2 |
| 標簽: |
沒有標簽, 成為第一個標記此記錄!
|
| _version_ | 1869530565655396352 |
|---|---|
| author | Bentert, Matthias |
| author_browse | Bentert, Matthias |
| author_facet | Bentert, Matthias |
| author_sort | Bentert, Matthias |
| collection | Directory of Open Access Books |
| description | This thesis presents faster (in terms of worst-case running times) exact algorithms for special cases of graph problems through dynamic programming and 2-SAT programming. Dynamic programming describes the procedure of breaking down a problem recursively into overlapping subproblems, that is, subproblems with common subsubproblems. Given optimal solutions to these subproblems, the dynamic program then combines them into an optimal solution for the original problem. 2-SAT programming refers to the procedure of reducing a problem to a set of 2-SAT formulas, that is, boolean formulas in conjunctive normal form in which each clause contains at most two literals. Computing whether such a formula is satisfiable (and computing a satisfying truth assignment, if one exists) takes linear time in the formula length. Hence, when satisfying truth assignments to some 2-SAT formulas correspond to a solution of the original problem and all formulas can be computed efficiently, that is, in polynomial time in the input size of the original problem, then the original problem can be solved in polynomial time. We next describe our main results. Diameter asks for the maximal distance between any two vertices in a given undirected graph. It is arguably among the most fundamental graph parameters. We provide both positive and negative parameterized results for distance-from-triviality-type parameters and parameter combinations that were observed to be small in real-world applications. In Length-Bounded Cut, we search for a bounded-size set of edges that intersects all paths between two given vertices of at most some given length. We confirm a conjecture from the literature by providing a polynomial-time algorithm for proper interval graphs which is based on dynamic programming. k-Disjoint Shortest Paths is the problem of finding (vertex-)disjoint paths between given vertex terminals such that each of these paths is a shortest path between the respective terminals. Its complexity for constant k > 2 has been an open problem for over 20 years. Using dynamic programming, we show that k-Disjoint Shortest Paths can be solved in polynomial time for each constant k. The problem Tree Containment asks whether a phylogenetic tree T is contained in a phylogenetic network N. A phylogenetic network (or tree) is a leaf-labeled single-source directed acyclic graph (or tree) in which each vertex has in-degree at most one or out-degree at most one. The problem stems from computational biology in the context of the tree of life (the history of speciation). We introduce a particular variant that resembles certain types of uncertainty in the input. We show that if each leaf label occurs at most twice in a phylogenetic tree N, then the problem can be solved in polynomial time and if labels can occur up to three times, then the problem becomes NP-hard. Lastly, Reachable Object is the problem of deciding whether there is a sequence of rational trades of objects among agents such that a given agent can obtain a certain object. A rational trade is a swap of objects between two agents where both agents profit from the swap, that is, they receive objects they prefer over the objects they trade away. This problem can be seen as a natural generalization of the well-known and well-studied Housing Market problem where the agents are arranged in a graph and only neighboring agents can trade objects. We prove a dichotomy result that states that the problem is polynomial-time solvable if each agent prefers at most two objects over its initially held object and it is NP-hard if each agent prefers at most three objects over its initially held object. We also provide a polynomial-time 2-SAT program for the case where the graph of agents is a cycle. |
| format | Online |
| id | doab-20.500.12854ir-81574 |
| institution | Directory of Open Access Books |
| language | eng |
| publishDate | 2022 |
| publishDateRange | 2022 |
| publishDateSort | 2022 |
| publisher | Universitätsverlag der Technischen Universität Berlin |
| publisherStr | Universitätsverlag der Technischen Universität Berlin |
| record_format | ojs |
| spelling | doab-20.500.12854ir-815742025-07-30T11:55:41Z Elements of dynamic and 2-SAT programming: paths, trees, and cuts Bentert, Matthias graph diameter shortest paths computation flow and cut problems resource allocation computational biology thema EDItEUR::U Computing and Information Technology::UM Computer programming / software engineering::UMB Algorithms and data structures thema EDItEUR::U Computing and Information Technology::UM Computer programming / software engineering::UMB Algorithms and data structures This thesis presents faster (in terms of worst-case running times) exact algorithms for special cases of graph problems through dynamic programming and 2-SAT programming. Dynamic programming describes the procedure of breaking down a problem recursively into overlapping subproblems, that is, subproblems with common subsubproblems. Given optimal solutions to these subproblems, the dynamic program then combines them into an optimal solution for the original problem. 2-SAT programming refers to the procedure of reducing a problem to a set of 2-SAT formulas, that is, boolean formulas in conjunctive normal form in which each clause contains at most two literals. Computing whether such a formula is satisfiable (and computing a satisfying truth assignment, if one exists) takes linear time in the formula length. Hence, when satisfying truth assignments to some 2-SAT formulas correspond to a solution of the original problem and all formulas can be computed efficiently, that is, in polynomial time in the input size of the original problem, then the original problem can be solved in polynomial time. We next describe our main results. Diameter asks for the maximal distance between any two vertices in a given undirected graph. It is arguably among the most fundamental graph parameters. We provide both positive and negative parameterized results for distance-from-triviality-type parameters and parameter combinations that were observed to be small in real-world applications. In Length-Bounded Cut, we search for a bounded-size set of edges that intersects all paths between two given vertices of at most some given length. We confirm a conjecture from the literature by providing a polynomial-time algorithm for proper interval graphs which is based on dynamic programming. k-Disjoint Shortest Paths is the problem of finding (vertex-)disjoint paths between given vertex terminals such that each of these paths is a shortest path between the respective terminals. Its complexity for constant k > 2 has been an open problem for over 20 years. Using dynamic programming, we show that k-Disjoint Shortest Paths can be solved in polynomial time for each constant k. The problem Tree Containment asks whether a phylogenetic tree T is contained in a phylogenetic network N. A phylogenetic network (or tree) is a leaf-labeled single-source directed acyclic graph (or tree) in which each vertex has in-degree at most one or out-degree at most one. The problem stems from computational biology in the context of the tree of life (the history of speciation). We introduce a particular variant that resembles certain types of uncertainty in the input. We show that if each leaf label occurs at most twice in a phylogenetic tree N, then the problem can be solved in polynomial time and if labels can occur up to three times, then the problem becomes NP-hard. Lastly, Reachable Object is the problem of deciding whether there is a sequence of rational trades of objects among agents such that a given agent can obtain a certain object. A rational trade is a swap of objects between two agents where both agents profit from the swap, that is, they receive objects they prefer over the objects they trade away. This problem can be seen as a natural generalization of the well-known and well-studied Housing Market problem where the agents are arranged in a graph and only neighboring agents can trade objects. We prove a dichotomy result that states that the problem is polynomial-time solvable if each agent prefers at most two objects over its initially held object and it is NP-hard if each agent prefers at most three objects over its initially held object. We also provide a polynomial-time 2-SAT program for the case where the graph of agents is a cycle. 2022-05-13T05:21:56Z 2022-05-13T05:21:56Z 2022-04-15T13:08:40Z 2021 book ONIX_20220415_9783798332096_2 OCN: 1367233189 2199-5249 https://library.oapen.org/handle/20.500.12657/54061 9783798332096 9783798332102 https://directory.doabooks.org/handle/20.500.12854/81574 eng Foundations of computing open access image/jpeg image/jpeg image/jpeg image/jpeg Attribution 4.0 International Attribution 4.0 International Attribution 4.0 International Attribution 4.0 International https://library.oapen.org/bitstream/20.500.12657/54061/1/bentert_matthias.pdf https://library.oapen.org/bitstream/20.500.12657/54061/1/bentert_matthias.pdf https://library.oapen.org/bitstream/20.500.12657/54061/1/bentert_matthias.pdf https://library.oapen.org/bitstream/20.500.12657/54061/1/bentert_matthias.pdf Universitätsverlag der Technischen Universität Berlin 10.14279/depositonce-11462 10.14279/depositonce-11462 e39576fc-df94-4af7-8fbe-4f7c2d6b68f3 9783798332096 9783798332102 AG Universitätsverlage 213 Berlin open access |
| spellingShingle | graph diameter shortest paths computation flow and cut problems resource allocation computational biology thema EDItEUR::U Computing and Information Technology::UM Computer programming / software engineering::UMB Algorithms and data structures thema EDItEUR::U Computing and Information Technology::UM Computer programming / software engineering::UMB Algorithms and data structures Bentert, Matthias Elements of dynamic and 2-SAT programming: paths, trees, and cuts |
| title | Elements of dynamic and 2-SAT programming: paths, trees, and cuts |
| title_full | Elements of dynamic and 2-SAT programming: paths, trees, and cuts |
| title_fullStr | Elements of dynamic and 2-SAT programming: paths, trees, and cuts |
| title_full_unstemmed | Elements of dynamic and 2-SAT programming: paths, trees, and cuts |
| title_short | Elements of dynamic and 2-SAT programming: paths, trees, and cuts |
| title_sort | elements of dynamic and 2 sat programming paths trees and cuts |
| topic | graph diameter shortest paths computation flow and cut problems resource allocation computational biology thema EDItEUR::U Computing and Information Technology::UM Computer programming / software engineering::UMB Algorithms and data structures thema EDItEUR::U Computing and Information Technology::UM Computer programming / software engineering::UMB Algorithms and data structures |
| topic_facet | graph diameter shortest paths computation flow and cut problems resource allocation computational biology thema EDItEUR::U Computing and Information Technology::UM Computer programming / software engineering::UMB Algorithms and data structures thema EDItEUR::U Computing and Information Technology::UM Computer programming / software engineering::UMB Algorithms and data structures |
| url | ONIX_20220415_9783798332096_2 |
| work_keys_str_mv | AT bentertmatthias elementsofdynamicand2satprogrammingpathstreesandcuts |