This thesis investigates the parameterized computational complexity of
\nsix classic graph problems lifted to a temporal setting. More
\nspecifically, we consider problems defined on temporal graphs, that is, a
\n graph where the edge set may change over a discrete time interval,
\nwhile the vertex set remains unchanged. Temporal graphs are well-suited
\nto model dynamic data and hence they are naturally motivated in contexts
\n where dynamic changes or time-dependent interactions play an important
\nrole, such as, for example, communication networks, social networks, or
\nphysical proximity networks. The most important selection criteria for
\nour problems was that they are well-motivated in the context of dynamic
\ndata analysis.
Since temporal graphs are mathematically more complex than static
\ngraphs, it is maybe not surprising that all problems we consider in this
\n thesis are NP-hard. We focus on the development of exact algorithms,
\nwhere our goal is to obtain fixed-parameter tractability results, and
\nrefined computational hardness reductions that either show NP-hardness
\nfor very restricted input instances or parameterized hardness with
\nrespect to \u201clarge\u201d parameters. In the context of temporal graphs, we
\nmostly consider structural parameters of the underlying graph, that is,
\nthe graph obtained by ignoring all time information. However, we also
\nconsider parameters of other types, such as ones trying to measure how
\nfast the temporal graph changes over time. In the following we briefly
\ndiscuss the problem setting and the main results.
Restless Temporal Paths. A path in a temporal graph has to respect
\ncausality, or time, which means that the edges used by a temporal path
\nhave to appear at non-decreasing times. We investigate temporal paths
\nthat additionally have a maximum waiting time in every vertex of the
\ntemporal graph. Our main contributions are establishing NP-hardness for
\nthe problem of finding restless temporal paths even in very restricted
\ncases, and showing W[1]-hardness with respect to the feedback vertex
\nnumber of the underlying graph.
Temporal Separators. A temporal separator is a vertex set that, when
\nremoved from the temporal graph, destroys all temporal paths between two
\n dedicated vertices. Our contribution here is twofold: Firstly, we
\ninvestigate the computational complexity of finding temporal separators
\nin temporal unit interval graphs, a generalization of unit interval
\ngraphs to the temporal setting. We show that the problem is NP-hard on
\ntemporal unit interval graphs but we identify an additional restriction
\nwhich makes the problem solvable in polynomial time. We use the latter
\nresult to develop a fixed-parameter algorithm with a
\n\u201cdistance-to-triviality\u201d parameterization. Secondly, we show that
\nfinding temporal separators that destroy all restless temporal paths is
\n\u03a3-P-2-hard.
Temporal Matchings. We introduce a model for matchings in temporal
\ngraphs, where, if two vertices are matched at some point in time, then
\nthey have to \u201crecharge\u201d afterwards, meaning that they cannot be matched
\nagain for a certain number of time steps. In our main result we employ
\ntemporal line graphs to show that finding matchings is NP-hard even on
\ninstances where the underlying graph is a path.
Temporal Coloring. We lift the classic graph coloring problem to the
\ntemporal setting. In our model, every edge has to be colored properly
\n(that is, the endpoints are colored differently) at least once in every
\ntime interval of a certain length. We show that this problem is NP-hard
\nin very restricted cases, even if we only have two colors. We present
\nsimple exponential-time algorithms to solve this problem. As a main
\ncontribution, we show that these algorithms presumably cannot be
\nimproved significantly.
Temporal Cliques and s-Plexes. We propose a model for temporal s-plexes
\nthat is a canonical generalization of an existing model for temporal
\ncliques. Our main contribution is a fixed-parameter algorithm that
\nenumerates all maximal temporal s-plexes in a given temporal graph,
\nwhere we use a temporal adaptation of degeneracy as a parameter.
Temporal Cluster Editing. We present a model for cluster editing in
\ntemporal graphs, where we want to edit all \u201clayers\u201d of a temporal graph
\ninto cluster graphs that are sufficiently similar. Our main contribution
\n is a fixed-parameter algorithm with respect to the parameter \u201cnumber of
\n edge modifications\u201d plus the \u201cmeasure of similarity\u201d of the resulting
\nclusterings. We further show that there is an efficient preprocessing
\nprocedure that can provably reduce the size of the input instance to be
\nindependent of the number of vertices of the original input instance.<\/p>","protected":false},"excerpt":{"rendered":"
This thesis investigates the parameterized computational complexity of
\nsix classic graph problems lifted to a temporal setting. More
\nspecifically, we consider problems defined on temporal graphs, that is, a
\n graph where the edge set may change over a discrete time interval,
\nwhile the vertex set remains unchanged. Temporal graphs are well-suited
\nto model dynamic data and hence they are naturally motivated in contexts
\n where dynamic changes or time-dependent interactions play an important
\nrole, such as, for example, communication networks, social networks, or
\nphysical proximity networks. The most important selection criteria for
\nour problems was that they are well-motivated in the context of dynamic
\ndata analysis.
Since temporal graphs are mathematically more complex than static
\ngraphs, it is maybe not surprising that all problems we consider in this
\n thesis are NP-hard. We focus on the development of exact algorithms,
\nwhere our goal is to obtain fixed-parameter tractability results, and
\nrefined computational hardness reductions that either show NP-hardness
\nfor very restricted input instances or parameterized hardness with
\nrespect to \u201clarge\u201d parameters. In the context of temporal graphs, we
\nmostly consider structural parameters of the underlying graph, that is,
\nthe graph obtained by ignoring all time information. However, we also
\nconsider parameters of other types, such as ones trying to measure how
\nfast the temporal graph changes over time. In the following we briefly
\ndiscuss the problem setting and the main results.
Restless Temporal Paths. A path in a temporal graph has to respect
\ncausality, or time, which means that the edges used by a temporal path
\nhave to appear at non-decreasing times. We investigate temporal paths
\nthat additionally have a maximum waiting time in every vertex of the
\ntemporal graph. Our main contributions are establishing NP-hardness for
\nthe problem of finding restless temporal paths even in very restricted
\ncases, and showing W[1]-hardness with respect to the feedback vertex
\nnumber of the underlying graph.
Temporal Separators. A temporal separator is a vertex set that, when
\nremoved from the temporal graph, destroys all temporal paths between two
\n dedicated vertices. Our contribution here is twofold: Firstly, we
\ninvestigate the computational complexity of finding temporal separators
\nin temporal unit interval graphs, a generalization of unit interval
\ngraphs to the temporal setting. We show that the problem is NP-hard on
\ntemporal unit interval graphs but we identify an additional restriction
\nwhich makes the problem solvable in polynomial time. We use the latter
\nresult to develop a fixed-parameter algorithm with a
\n\u201cdistance-to-triviality\u201d parameterization. Secondly, we show that
\nfinding temporal separators that destroy all restless temporal paths is
\n\u03a3-P-2-hard.
Temporal Matchings. We introduce a model for matchings in temporal
\ngraphs, where, if two vertices are matched at some point in time, then
\nthey have to \u201crecharge\u201d afterwards, meaning that they cannot be matched
\nagain for a certain number of time steps. In our main result we employ
\ntemporal line graphs to show that finding matchings is NP-hard even on
\ninstances where the underlying graph is a path.
Temporal Coloring. We lift the classic graph coloring problem to the
\ntemporal setting. In our model, every edge has to be colored properly
\n(that is, the endpoints are colored differently) at least once in every
\ntime interval of a certain length. We show that this problem is NP-hard
\nin very restricted cases, even if we only have two colors. We present
\nsimple exponential-time algorithms to solve this problem. As a main
\ncontribution, we show that these algorithms presumably cannot be
\nimproved significantly.
Temporal Cliques and s-Plexes. We propose a model for temporal s-plexes
\nthat is a canonical generalization of an existing model for temporal
\ncliques. Our main contribution is a fixed-parameter algorithm that
\nenumerates all maximal temporal s-plexes in a given temporal graph,
\nwhere we use a temporal adaptation of degeneracy as a parameter.
Temporal Cluster Editing. We present a model for cluster editing in
\ntemporal graphs, where we want to edit all \u201clayers\u201d of a temporal graph
\ninto cluster graphs that are sufficiently similar. Our main contribution
\n is a fixed-parameter algorithm with respect to the parameter \u201cnumber of
\n edge modifications\u201d plus the \u201cmeasure of similarity\u201d of the resulting
\nclusterings. We further show that there is an efficient preprocessing
\nprocedure that can provably reduce the size of the input instance to be
\nindependent of the number of vertices of the original input instance.<\/p>\n","protected":false},"featured_media":6734,"comment_status":"open","ping_status":"closed","template":"","meta":{"_acf_changed":false},"class_list":["post-6733","product","type-product","status-publish","has-post-thumbnail","hentry","product_cat-institut-fuer-softwaretechnik-und-theoretische-informatik","autor-hendrik-molter","reihe-foundations-of-computing","edition-universitaetsverlag-tu-berlin"],"acf":[],"_links":{"self":[{"href":"https:\/\/verlag.tu-berlin.de\/en\/wp-json\/wp\/v2\/product\/6733","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/verlag.tu-berlin.de\/en\/wp-json\/wp\/v2\/product"}],"about":[{"href":"https:\/\/verlag.tu-berlin.de\/en\/wp-json\/wp\/v2\/types\/product"}],"replies":[{"embeddable":true,"href":"https:\/\/verlag.tu-berlin.de\/en\/wp-json\/wp\/v2\/comments?post=6733"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/verlag.tu-berlin.de\/en\/wp-json\/wp\/v2\/media\/6734"}],"wp:attachment":[{"href":"https:\/\/verlag.tu-berlin.de\/en\/wp-json\/wp\/v2\/media?parent=6733"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}