Elements of dynamic and 2-SAT programming : : paths, trees, and cuts / / Matthias Bentert.
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:
Superior document: | Foundations of computing |
---|---|
VerfasserIn: | |
Place / Publishing House: | Berlin : : Universitätsverlag der Technischen Universität Berlin,, 2021. |
Year of Publication: | 2021 |
Language: | English |
Series: | Foundations of computing.
|
Physical Description: | 1 online resource (213 pages). |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
id |
993562546904498 |
---|---|
ctrlnum |
(CKB)4920000001372344 (NjHacI)994920000001372344 (EXLCZ)994920000001372344 |
collection |
bib_alma |
record_format |
marc |
spelling |
Bentert, Matthias, author. Elements of dynamic and 2-SAT programming : paths, trees, and cuts / Matthias Bentert. Elements of dynamic and 2-SAT programming Berlin : Universitätsverlag der Technischen Universität Berlin, 2021. 1 online resource (213 pages). text txt rdacontent computer c rdamedia online resource cr rdacarrier Foundations of computing Description based on: online resource; title from PDF information screen (Universitätsverlag der Technischen Universität Berlin, viewed February 21, 2023.). 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. In English. Computational biology. 3-7983-3209-6 Foundations of computing. |
language |
English |
format |
eBook |
author |
Bentert, Matthias, |
spellingShingle |
Bentert, Matthias, Elements of dynamic and 2-SAT programming : paths, trees, and cuts / Foundations of computing |
author_facet |
Bentert, Matthias, |
author_variant |
m b mb |
author_role |
VerfasserIn |
author_sort |
Bentert, Matthias, |
title |
Elements of dynamic and 2-SAT programming : paths, trees, and cuts / |
title_sub |
paths, trees, and cuts / |
title_full |
Elements of dynamic and 2-SAT programming : paths, trees, and cuts / Matthias Bentert. |
title_fullStr |
Elements of dynamic and 2-SAT programming : paths, trees, and cuts / Matthias Bentert. |
title_full_unstemmed |
Elements of dynamic and 2-SAT programming : paths, trees, and cuts / Matthias Bentert. |
title_auth |
Elements of dynamic and 2-SAT programming : paths, trees, and cuts / |
title_alt |
Elements of dynamic and 2-SAT programming |
title_new |
Elements of dynamic and 2-SAT programming : |
title_sort |
elements of dynamic and 2-sat programming : paths, trees, and cuts / |
series |
Foundations of computing |
series2 |
Foundations of computing |
publisher |
Universitätsverlag der Technischen Universität Berlin, |
publishDate |
2021 |
physical |
1 online resource (213 pages). |
isbn |
3-7983-3209-6 |
callnumber-first |
Q - Science |
callnumber-subject |
QH - Natural History and Biology |
callnumber-label |
QH324 |
callnumber-sort |
QH 3324.2 B468 42021 |
illustrated |
Not Illustrated |
dewey-hundreds |
500 - Science |
dewey-tens |
570 - Life sciences; biology |
dewey-ones |
570 - Life sciences; biology |
dewey-full |
570.285 |
dewey-sort |
3570.285 |
dewey-raw |
570.285 |
dewey-search |
570.285 |
work_keys_str_mv |
AT bentertmatthias elementsofdynamicand2satprogrammingpathstreesandcuts AT bentertmatthias elementsofdynamicand2satprogramming |
status_str |
n |
ids_txt_mv |
(CKB)4920000001372344 (NjHacI)994920000001372344 (EXLCZ)994920000001372344 |
carrierType_str_mv |
cr |
hierarchy_parent_title |
Foundations of computing |
is_hierarchy_title |
Elements of dynamic and 2-SAT programming : paths, trees, and cuts / |
container_title |
Foundations of computing |
_version_ |
1764993842688294912 |
fullrecord |
<?xml version="1.0" encoding="UTF-8"?><collection xmlns="http://www.loc.gov/MARC21/slim"><record><leader>04900nam a2200313 i 4500</leader><controlfield tag="001">993562546904498</controlfield><controlfield tag="005">20230221151241.0</controlfield><controlfield tag="006">m o d </controlfield><controlfield tag="007">cr |||||||||||</controlfield><controlfield tag="008">230221s2021 gw o 000 0 eng d</controlfield><datafield tag="035" ind1=" " ind2=" "><subfield code="a">(CKB)4920000001372344</subfield></datafield><datafield tag="035" ind1=" " ind2=" "><subfield code="a">(NjHacI)994920000001372344</subfield></datafield><datafield tag="035" ind1=" " ind2=" "><subfield code="a">(EXLCZ)994920000001372344</subfield></datafield><datafield tag="040" ind1=" " ind2=" "><subfield code="a">NjHacI</subfield><subfield code="b">eng</subfield><subfield code="e">rda</subfield><subfield code="c">NjHacl</subfield></datafield><datafield tag="050" ind1=" " ind2="4"><subfield code="a">QH324.2</subfield><subfield code="b">.B468 2021</subfield></datafield><datafield tag="082" ind1="0" ind2="4"><subfield code="a">570.285</subfield><subfield code="2">23</subfield></datafield><datafield tag="100" ind1="1" ind2=" "><subfield code="a">Bentert, Matthias,</subfield><subfield code="e">author.</subfield></datafield><datafield tag="245" ind1="1" ind2="0"><subfield code="a">Elements of dynamic and 2-SAT programming :</subfield><subfield code="b">paths, trees, and cuts /</subfield><subfield code="c">Matthias Bentert.</subfield></datafield><datafield tag="246" ind1=" " ind2=" "><subfield code="a">Elements of dynamic and 2-SAT programming</subfield></datafield><datafield tag="264" ind1=" " ind2="1"><subfield code="a">Berlin :</subfield><subfield code="b">Universitätsverlag der Technischen Universität Berlin,</subfield><subfield code="c">2021.</subfield></datafield><datafield tag="300" ind1=" " ind2=" "><subfield code="a">1 online resource (213 pages).</subfield></datafield><datafield tag="336" ind1=" " ind2=" "><subfield code="a">text</subfield><subfield code="b">txt</subfield><subfield code="2">rdacontent</subfield></datafield><datafield tag="337" ind1=" " ind2=" "><subfield code="a">computer</subfield><subfield code="b">c</subfield><subfield code="2">rdamedia</subfield></datafield><datafield tag="338" ind1=" " ind2=" "><subfield code="a">online resource</subfield><subfield code="b">cr</subfield><subfield code="2">rdacarrier</subfield></datafield><datafield tag="490" ind1="1" ind2=" "><subfield code="a">Foundations of computing</subfield></datafield><datafield tag="588" ind1=" " ind2=" "><subfield code="a">Description based on: online resource; title from PDF information screen (Universitätsverlag der Technischen Universität Berlin, viewed February 21, 2023.).</subfield></datafield><datafield tag="520" ind1=" " ind2=" "><subfield code="a">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.</subfield></datafield><datafield tag="546" ind1=" " ind2=" "><subfield code="a">In English.</subfield></datafield><datafield tag="650" ind1=" " ind2="0"><subfield code="a">Computational biology.</subfield></datafield><datafield tag="776" ind1=" " ind2=" "><subfield code="z">3-7983-3209-6</subfield></datafield><datafield tag="830" ind1=" " ind2="0"><subfield code="a">Foundations of computing.</subfield></datafield><datafield tag="906" ind1=" " ind2=" "><subfield code="a">BOOK</subfield></datafield><datafield tag="ADM" ind1=" " ind2=" "><subfield code="b">2023-03-01 00:20:05 Europe/Vienna</subfield><subfield code="f">system</subfield><subfield code="c">marc21</subfield><subfield code="a">2022-09-22 08:09:39 Europe/Vienna</subfield><subfield code="g">false</subfield></datafield><datafield tag="AVE" ind1=" " ind2=" "><subfield code="P">DOAB Directory of Open Access Books</subfield><subfield code="x">https://eu02.alma.exlibrisgroup.com/view/uresolver/43ACC_OEAW/openurl?u.ignore_date_coverage=true&portfolio_pid=5337843630004498&Force_direct=true</subfield><subfield code="Z">5337843630004498</subfield><subfield code="8">5337843630004498</subfield></datafield></record></collection> |