Search

Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G , a temporal graph is represented by assigning a set of integer time-labels to every edge e of G , indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching , taking into account the dynamic nature of temporal graphs. In our problem, Maximum Temporal Matching , we are looking for the largest possible number of time-labeled edges (simply time-edges) (e , t) such that no vertex is matched more than once within any time window of Δ consecutive time slots, where Δ ∈ N is given. We prove strong computational hardness results for Maximum Temporal Matching , even for elementary cases, as well as fixed-parameter algorithms with respect to natural parameters and polynomial-time approximation algorithms. [ABSTRACT FROM AUTHOR]

The problem of deletion of vertices to a hereditary graph class is a well-studied problem in parameterized complexity. Recently, a natural extension of the problem was initiated where we are given a finite set of hereditary graph classes and we determine whether k vertices can be deleted from a given graph so that the connected components of the resulting graph belong to one of the given hereditary graph classes. The problem is shown to be fixed parameter tractable (FPT) when the deletion problem to each of the given hereditary graph classes is fixed-parameter tractable, and the property of being in any of the graph classes is expressible in the counting monodic second order (CMSO) logic. This paper focuses on pairs of specific graph classes (Π 1 , Π 2) in which we would like the connected components of the resulting graph to belong to, and design simpler and more efficient FPT algorithms. [ABSTRACT FROM AUTHOR]

We study the NP-hard Temporal (s , z) -Separation problem on temporal graphs, which are graphs with fixed vertex sets but edge sets that change over discrete time steps. We tackle Temporal (s , z) -Separation by restricting the layers (i.e., graphs characterized by edges that are present at a certain point in time) to specific graph classes. We restrict the layers of the temporal graphs to be either all split graphs or all permutation graphs (both being perfect graph classes) and provide both intractability and tractability results. In particular, we show that in general Temporal (s , z) -Separation remains NP-hard both on temporal split and temporal permutation graphs, but we also spot promising islands of fixed-parameter tractability particularly based on parameterizations that measure the amount of "change over time". [ABSTRACT FROM AUTHOR]

We study the fixed-parameter tractability of the problem of deciding whether a given temporal graph admits a temporal walk that visits all vertices (temporal exploration) or, in some variants, a certain subset of the vertices. In the strict variant, edges must be traversed in strictly increasing timesteps; in the non-strict variant, any number of edges can be traversed in each timestep. For both variants, we give FPT algorithms for finding a temporal walk that visits a given set X of vertices, parameterised by | X | , and for finding a temporal walk that visits at least k distinct vertices, parameterised by k. We also show W [ 2 ] -hardness for a set version of temporal exploration. For the non-strict variant, we give an FPT algorithm for temporal exploration parameterised by the lifetime, and show that temporal exploration can be solved in polynomial time if the graph in each timestep has at most two connected components. [ABSTRACT FROM AUTHOR]

While structural width parameters (of the input) belong to the standard toolbox of graph algorithms, it is not the usual case in computational geometry. As a case study we propose a natural extension of the structural graph parameter of clique-width to geometric point configurations represented by their order type. We study basic properties of this clique-width notion, and show that it is aligned with the general concept of clique-width of relational structures by Blumensath and Courcelle (2006). We also relate the new notion to monadic second-order logic of point configurations. As an application, we provide several linear FPT time algorithms for geometric point problems which are NP-hard in general, in the special case that the input point set is of bounded clique-width and the clique-width expression is also given. [ABSTRACT FROM AUTHOR]

We provide new parameterized complexity results for Interval Scheduling on Eligible Machines. In this problem, a set of n jobs is given to be processed non-preemptively on a set of m machines. Each job has a processing time , a deadline , a weight , and a set of eligible machines that can process it. The goal is to find a maximum weight subset of jobs that can each be processed on one of its eligible machines such that it completes exactly at its deadline. We focus on two parameters: The number m of machines, and the largest processing time p max. Our main contribution is showing W[1] -hardness when parameterized by m. This answers Open Problem 8 of Mnich and van Bevern's list of 15 open problems in parameterized complexity of scheduling problems [Computers & Operations Research, 2018]. Furthermore, we show NP -hardness even when p max = O (1) and present an FPT -algorithm with for the combined parameter m + p max. [ABSTRACT FROM AUTHOR]

Token Sliding Optimization asks whether there exists a sequence of at most ℓ steps that transforms independent set S into T , where at each step a token slides to an unoccupied neighboring vertex (while maintaining independence). In Token Jumping Optimization , we are instead allowed to jump from a vertex to any unoccupied vertex. Both problems are known to be FPT when parameterized by ℓ on nowhere dense graphs. In this work, we show that both problems are FPT for parameter k + ℓ + d on d -degenerate graphs as well as for parameter | M | + ℓ + Δ on graphs having a modulator M to maximum degree Δ. We complement these results by showing that for parameter ℓ both problems become hard already on 2-degenerate graphs. Finally, we show that using such families one can obtain a unified algorithm for the standard Token Jumping problem parameterized by k on degenerate and nowhere dense graphs. [ABSTRACT FROM AUTHOR]

Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which often stand in contrast to practice where data is inherently dynamic. A temporal graph has an edge set that changes over time. We present a natural temporal extension of the classical graph coloring problem. Given a temporal graph and integers k and Δ, we ask for a coloring sequence with at most k colors for each vertex such that in every time window of Δ consecutive time steps, in which an edge is present, this edge is properly colored at least once. We thoroughly investigate the computational complexity of this temporal coloring problem. More specifically, we prove strong computational hardness results, complemented by efficient exact and approximation algorithms. [ABSTRACT FROM AUTHOR]

Given an undirected graph G = (V , E) the NP-hard Strong Triadic Closure (STC) problem asks for a labeling of the edges as weak and strong such that at most k edges are weak and for each induced P 3 in G at least one edge is weak. We study the following generalizations of STC with c different strong edge colors. In Multi-STC an induced P 3 may receive two strong labels as long as they are different. In Edge-List Multi-STC and Vertex-List Multi-STC we may restrict the set of permitted colors for each edge of G. We show that, under the Exponential Time Hypothesis (ETH), Edge-List Multi-STC and Vertex-List Multi-STC cannot be solved in time 2 o (| V | 2). We proceed with a parameterized complexity analysis in which we extend previous algorithms and kernelizations for STC [11,14] to the three variants or outline the limits of such an extension. [ABSTRACT FROM AUTHOR]

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information spread over social networks and biological diseases spreading over contact networks. Often, the networks over which these processes spread are dynamic in nature, and can be modelled with temporal graphs. Here, we study the problem of deleting edges from a given temporal graph in order to reduce the number of vertices (temporally) reachable from a given starting point. This could be used to control the spread of a disease, rumour, etc. in a temporal graph. In particular, our aim is to find a temporal subgraph in which a process starting at any single vertex can be transferred to only a limited number of other vertices using a temporally-feasible path. We introduce a natural edge-deletion problem for temporal graphs and provide positive and negative results on its computational complexity and approximability. [ABSTRACT FROM AUTHOR]

This paper studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks. We describe a polynomial-time algorithm for deciding whether an undirected nonbinary phylogenetic network, given the locations of the root and reticulation vertices, can be oriented as a directed nonbinary phylogenetic network. Moreover, we characterize when this is possible and show that, in such instances, the resulting directed nonbinary phylogenetic network is unique. In addition, without being given the location of the root and the reticulation vertices, we describe an algorithm for deciding whether an undirected binary phylogenetic network N can be oriented as a directed binary phylogenetic network of a certain class. The algorithm is fixed-parameter tractable (FPT) when the parameter is the level of N and is applicable to classes of directed phylogenetic networks that satisfy certain conditions. As an example, we show that the well-studied class of binary tree-child networks satisfies these conditions. [ABSTRACT FROM AUTHOR]

We study the NP-complete Minimum Shared Edges (MSE) problem, defined as follows. Given an undirected graph, a source and a sink vertex, and two integers p and k , we ask whether there are p paths in the graph connecting the source with the sink and sharing at most k edges. Herein, an edge is shared if it appears in at least two paths. On the positive side, we show that MSE is fixed-parameter tractable with respect to p. On the negative side, we show that MSE is W [ 1 ] -hard when parameterized by the treewidth of the input graph and the number k of shared edges combined, and that MSE does not admit a polynomial-size kernel with respect to p (unless NP ⊆ coNP / poly). [ABSTRACT FROM AUTHOR]

The topological theory for semi-complete digraphs, pioneered by Chudnovsky, Fradkin, Kim, Scott, and Seymour [10–12,28,43,39] , concentrates on the interplay between the most important width measures — cutwidth and pathwidth — and containment relations like topological/minor containment or immersion. We propose a new approach to this theory that is based on outdegree orderings and new families of obstacles for cutwidth and pathwidth. Using the new approach we are able to reprove the most important known results in a unified and simplified manner, as well as provide multiple improvements. Notably, we obtain a number of efficient approximation and fixed-parameter tractable algorithms for computing width measures of semi-complete digraphs, as well as fast fixed-parameter tractable algorithms for testing containment relations in the semi-complete setting. As a direct corollary of our work, we also derive explicit and essentially tight bounds on duality relations between width parameters and containment orderings in semi-complete digraphs. [ABSTRACT FROM AUTHOR]

We study the complexity of a generic hitting problem H - Subgraph Hitting , where given a fixed pattern graph H and an input graph G , the task is to find a set X ⊆ V ( G ) of minimum size that hits all subgraphs of G isomorphic to H . In the colorful variant of the problem, each vertex of G is precolored with some color from V ( H ) and we require to hit only H -subgraphs with matching colors. Standard techniques shows that for every fixed H , the problem is fixed-parameter tractable parameterized by the treewidth of G ; however, it is not clear how exactly the running time should depend on treewidth. For the colorful variant, we demonstrate matching upper and lower bounds showing that the dependence of the running time on treewidth of G is tightly governed by μ ( H ) , the maximum size of a minimal vertex separator in H . That is, we show for every fixed H that, on a graph of treewidth t , the colorful problem can be solved in time 2 O ( t μ ( H ) ) ⋅ | V ( G ) | , but cannot be solved in time 2 o ( t μ ( H ) ) ⋅ | V ( G ) | O ( 1 ) , assuming the Exponential Time Hypothesis (ETH). Furthermore, we give some preliminary results showing that, in the absence of colors, the parameterized complexity landscape of H - Subgraph Hitting is much richer. [ABSTRACT FROM AUTHOR]

We study the computational complexity of k -anonymizing a given graph by as few graph contractions as possible. A graph is said to be k -anonymous if for every vertex in it, there are at least k − 1 other vertices with exactly the same degree. The general degree anonymization problem is motivated by applications in privacy-preserving data publishing, and was studied to some extent for various graph operations (most notable operations being edge addition, edge deletion, vertex addition, and vertex deletion). We complement this line of research by studying the computational complexity of degree anonymization by graph contractions. We consider several variants of graph contractions, which are operations of interest, for example, in the contexts of social networks and clustering algorithms. We show that the problem of degree anonymization by graph contractions is NP -hard even for some very restricted inputs, and identify some fixed-parameter tractable cases. [ABSTRACT FROM AUTHOR]

Given a finite set X , a collection T of rooted phylogenetic trees on X and an integer k , the Hybridization Number problem asks if there exists a phylogenetic network on X that displays all trees from T and has reticulation number at most k . We show two kernelization algorithms for Hybridization Number , with kernel sizes 4 k ( 5 k ) t and 20 k 2 ( Δ + − 1 ) respectively, with t the number of input trees and Δ + their maximum outdegree. Experiments on simulated data demonstrate the practical relevance of our kernelization algorithms. In addition, we present an n f ( k ) t -time algorithm, with n = | X | and f some computable function of k . [ABSTRACT FROM AUTHOR]

The NP-hard Distinct Vectors problem asks to delete as many columns as possible from a matrix such that all rows in the resulting matrix are still pairwise distinct. Our main result is that, for binary matrices, there is a complexity dichotomy for Distinct Vectors based on the maximum ( H ) and the minimum ( h ) pairwise Hamming distance between matrix rows: Distinct Vectors can be solved in polynomial time if H ≤ 2 ⌈ h / 2 ⌉ + 1 , and is NP-complete otherwise. Moreover, we explore connections of Distinct Vectors to hitting sets, thereby providing several fixed-parameter tractability and intractability results also for general matrices. [ABSTRACT FROM AUTHOR]

We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the side of fixed-parameter tractability. Other than for its famous sister problem Stable Marriage which focuses on a bipartite scenario, Stable Roommates with Incomplete Lists allows for arbitrary acceptability graphs whose edges specify the possible matchings of each two agents (agents are represented by graph vertices). Herein, incomplete lists and ties reflect the fact that in realistic application scenarios the agents cannot bring all other agents into a linear order. Among our main contributions is to show that it is W[1]-hard to compute a maximum-cardinality stable matching for acceptability graphs of bounded treedepth, bounded tree-cut width, and bounded disjoint paths modulator number (these are each time the respective parameters). Moreover, we obtain that 'only' asking for perfect stable matchings or the mere existence of a stable matching is fixed-parameter tractable with respect to tree-cut width but not with respect to treedepth. On the positive side, we also provide fixed-parameter tractability results for the parameter feedback edge set number. [ABSTRACT FROM AUTHOR]

Abstract: We prove that weighted circuit satisfiability for monotone or antimonotone circuits has no fixed-parameter tractable approximation algorithm with any approximation ratio function ρ, unless . In particular, not having such an fpt-approximation algorithm implies that these problems have no polynomial-time approximation algorithms with ratio for any nontrivial function ρ. [Copyright &y& Elsevier]

Abstract: We address in this paper a new computational biology problem that aims at understanding a mechanism that could potentially be used to genetically manipulate natural insect populations infected by inherited, intra-cellular parasitic bacteria. In this problem, that we denote by Mod/Resc Parsimony Inference, we are given a boolean matrix and the goal is to find two other boolean matrices with a minimum number of columns such that an appropriately defined operation on these matrices gives back the input. We show that this is formally equivalent to the Biclique Edge Cover for Bipartite Graphs problem and derive some complexity results for our problem using this equivalence. We provide a new, fixed-parameter tractability approach for solving both problems that slightly improves upon a previously published algorithm for the Biclique Edge Cover for Bipartite Graphs. Finally, we present experimental results applying some of our techniques to a real-life dataset. [Copyright &y& Elsevier]

Abstract: We present a first thorough theoretical analysis of the Transitivity Editing problem on digraphs. Herein, the task is to make a given digraph transitive by a minimum number of arc insertions or deletions. Transitivity Editing has applications in the detection of hierarchical structure in molecular characteristics of diseases. We demonstrate that if the input digraph does not contain “diamonds”, then there is an optimal solution that performs only arc deletions. This fact helps us construct a first proof of NP-hardness, which also extends to the restricted cases in which the input digraph is acyclic or has maximum degree three. By providing an -vertex problem kernel, we answer an open question from the literature. In case of digraphs with maximum degree d, an -vertex problem kernel can be shown. Moreover, we improve previous fixed-parameter algorithms, now achieving a running time of for an n-vertex digraph if k arc modifications are sufficient to make it transitive. Our hardness as well as algorithmic results transfer to Transitivity Deletion, where only arc deletions are allowed. [Copyright &y& Elsevier]

Abstract: We propose an effective polynomial-time preprocessing strategy for intractable median problems. Developing a new methodological framework, we show that if the input objects of generally intractable problems exhibit a sufficiently high degree of similarity between each other on average, then there are efficient exact solving algorithms. In other words, we show that the median problems Swap Median Permutation, Consensus Clustering, Kemeny Score, and Kemeny Tie Score all are fixed-parameter tractable with respect to the parameter “average distance between input objects”. To this end, we develop the novel concept of “partial kernelization” and, furthermore, identify polynomial-time solvable special cases for the considered problems. [Copyright &y& Elsevier]

Abstract: We study the parameterized complexity of several minimum label graph problems, in which we are given an undirected graph whose edges are labeled, and a property Π, and we are asked to find a subset of edges satisfying property Π with respect to G that uses the minimum number of labels. These problems have a lot of applications in networking. We show that all the problems under consideration are W[2]-hard when parameterized by the number of used labels, and that they remain W[2]-hard even on graphs whose pathwidth is bounded above by a small constant. On the positive side, we prove that most of these problems are FPT when parameterized by the solution size, that is, the size of the sought edge set. For example, we show that computing a maximum matching or an edge dominating set that uses the minimum number of labels, is FPT when parameterized by the solution size. Proving that some of these problems are FPT requires interesting algorithmic methods that we develop in this paper. [ABSTRACT FROM AUTHOR]

Abstract: We develop an algorithmically useful refinement of a forbidden submatrix characterization of 0/1-matrices fulfilling the Consecutive Ones Property (C1P). This characterization finds applications in new polynomial-time approximation algorithms and fixed-parameter tractability results for the NP-hard problem to delete a minimum number of rows or columns from a 0/1-matrix such that the remaining submatrix has the C1P. [Copyright &y& Elsevier]

Abstract: We show that the two NP-complete problems of Dodgson Score and Young Score have differing computational complexities when the winner is close to being a Condorcet winner. On the one hand, we present an efficient fixed-parameter algorithm for determining a Condorcet winner in Dodgson elections by a minimum number of switches in the votes. On the other hand, we prove that the corresponding problem for Young elections, where one has to delete votes instead of performing switches, is W[2]-complete. In addition, we study Dodgson elections that allow ties between the candidates and give fixed-parameter tractability as well as W[2]-completeness results depending on the cost model for switching ties. [Copyright &y& Elsevier]

Abstract: We consider new parameterizations of NP-optimization problems that have nontrivial lower and/or upper bounds on their optimum solution size. The natural parameter, we argue, is the quantity above the lower bound or below the upper bound. We show that for every problem in MAX SNP, the optimum value is bounded below by an unbounded function of the input-size, and that the above-guarantee parameterization with respect to this lower bound is fixed-parameter tractable. We also observe that approximation algorithms give nontrivial lower or upper bounds on the solution size and that the above or below guarantee question with respect to these bounds is fixed-parameter tractable for a subclass of NP-optimization problems. We then introduce the notion of ‘tight’ lower and upper bounds and exhibit a number of problems for which the above-guarantee and below-guarantee parameterizations with respect to a tight bound is fixed-parameter tractable or W-hard. We show that if we parameterize “sufficiently” above or below the tight bounds, then these parameterized versions are not fixed-parameter tractable unless , for a subclass of NP-optimization problems. We also list several directions to explore in this paradigm. [Copyright &y& Elsevier]

Abstract: We show that the NP-complete Feedback Vertex Set problem, which asks for the smallest set of vertices to remove from a graph to destroy all cycles, is deterministically solvable in time. Here, m denotes the number of graph edges, k denotes the size of the feedback vertex set searched for, and c is a constant. We extend this to an algorithm enumerating all solutions in time for a (larger) constant d. As a further result, we present a fixed-parameter algorithm with runtime for the NP-complete Edge Bipartization problem, which asks for at most k edges to remove from a graph to make it bipartite. [Copyright &y& Elsevier]

Abstract: Motivated by recent results showing that there are natural parameterized problems that are fixed-parameter tractable, but can only be solved by fixed-parameter tractable algorithms the running time of which depends nonelementarily on the parameter, we propose a notion of bounded fixed-parameter tractability, where the dependence of the running time on the parameter is restricted to be singly exponential. We develop a basic theory that is centred around the class EPT of tractable problems and an EW-hierarchy of classes of intractable problems, both in the bounded sense. By and large, this theory is similar to the established unbounded parameterized complexity theory, but there are some remarkable differences. Most notably, certain natural model-checking problems that are known to be fixed-parameter tractable in the unbounded sense have a very high complexity in the bounded theory. The problem of computing the VC-dimension of a family of sets, which is known to be complete for the class in the unbounded theory, is complete for the class in the bounded theory. It turns out that our bounded parameterized complexity theory is closely related to the classical complexity theory of problems that can be solved by a nondeterministic polynomial time algorithm that only uses nondeterministic bits, and in particular to the classes LOGSNP and LOGNP introduced by Papadimitriou and Yannakakis. [Copyright &y& Elsevier]

Abstract: We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times and , where n is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general “annotated” problem on black/white graphs that asks for a set of k vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved. [Copyright &y& Elsevier]

We discuss general techniques, centered around the “Layerwise Separation Property” (LSP) of a planar graph problem, that allow to develop algorithms with running time c√ of k&z.sfnc;G&z.sfnc;, given an instance G of a problem on planar graphs with parameter k. Problems having LSP include planar vertex cover, planar independent set, and planar dominating set. Extensions of our speed-up technique to basically all fixed-parameter tractable planar graph problems are also exhibited. Moreover, we relate, e.g., the domination number or the vertex cover number, with the treewidth of a plane graph. [Copyright &y& Elsevier]