77 results on '"Niedermeier, Rolf"'
Search Results
2. On Finding Separators in Temporal Split and Permutation Graphs
- Author
-
Maack, Nicolas, Molter, Hendrik, Niedermeier, Rolf, Renken, Malte, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bampis, Evripidis, editor, and Pagourtzis, Aris, editor
- Published
- 2021
- Full Text
- View/download PDF
3. Enumerating Isolated Cliques in Temporal Networks
- Author
-
Molter, Hendrik, Niedermeier, Rolf, Renken, Malte, Kacprzyk, Janusz, Series Editor, Cherifi, Hocine, editor, Gaito, Sabrina, editor, Mendes, José Fernendo, editor, Moro, Esteban, editor, and Rocha, Luis Mateus, editor
- Published
- 2020
- Full Text
- View/download PDF
4. Parameterized Dynamic Cluster Editing
- Author
-
Luo, Junjie, Molter, Hendrik, Nichterlein, André, and Niedermeier, Rolf
- Published
- 2021
- Full Text
- View/download PDF
5. Efficient algorithms for measuring the funnel-likeness of DAGs
- Author
-
Garlet Millani, Marcelo, Molter, Hendrik, Niedermeier, Rolf, and Sorge, Manuel
- Published
- 2020
- Full Text
- View/download PDF
6. A Parameterized Algorithmics Framework for Degree Sequence Completion Problems in Directed Graphs
- Author
-
Bredereck, Robert, Froese, Vincent, Koseler, Marcel, Garlet Millani, Marcelo, Nichterlein, André, and Niedermeier, Rolf
- Published
- 2019
- Full Text
- View/download PDF
7. Adapting the Bron–Kerbosch algorithm for enumerating maximal cliques in temporal graphs
- Author
-
Himmel, Anne-Sophie, Molter, Hendrik, Niedermeier, Rolf, and Sorge, Manuel
- Published
- 2017
- Full Text
- View/download PDF
8. A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
- Author
-
van Bevern, René, Niedermeier, Rolf, and Suchý, Ondřej
- Published
- 2017
- Full Text
- View/download PDF
9. Graph-Modeled Data Clustering: Fixed-Parameter Algorithms for Clique Generation
- Author
-
Gramm, Jens, Guo, Jiong, Hüffner, Falk, Niedermeier, Rolf, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Petreschi, Rossella, editor, Persiano, Giuseppe, editor, and Silvestri, Riccardo, editor
- Published
- 2003
- Full Text
- View/download PDF
10. Using Patterns to Form Homogeneous Teams
- Author
-
Bredereck, Robert, Köhler, Thomas, Nichterlein, André, Niedermeier, Rolf, and Philip, Geevarghese
- Published
- 2015
- Full Text
- View/download PDF
11. The effect of homogeneity on the computational complexity of combinatorial data anonymization
- Author
-
Bredereck, Robert, Nichterlein, André, Niedermeier, Rolf, and Philip, Geevarghese
- Published
- 2014
- Full Text
- View/download PDF
12. The Parameterized Complexity of Local Search for TSP, More Refined
- Author
-
Guo, Jiong, Hartung, Sepp, Niedermeier, Rolf, and Suchý, Ondřej
- Published
- 2013
- Full Text
- View/download PDF
13. On tractable cases of Target Set Selection
- Author
-
Nichterlein, André, Niedermeier, Rolf, Uhlmann, Johannes, and Weller, Mathias
- Published
- 2013
- Full Text
- View/download PDF
14. Approximation and Tidying—A Problem Kernel for s-Plex Cluster Vertex Deletion
- Author
-
van Bevern, René, Moser, Hannes, and Niedermeier, Rolf
- Published
- 2012
- Full Text
- View/download PDF
15. Computing Maximum Matchings in Temporal Graphs
- Author
-
Mertzios, George B., Molter, Hendrik, Niedermeier, Rolf, Zamaraev, Viktor, Zschoche, Philipp, Paul, Christophe, Bläser, Markus, and Blaser, Markus
- Subjects
FOS: Computer and information sciences ,History ,General Computer Science ,Polymers and Plastics ,Discrete Mathematics (cs.DM) ,Computer Networks and Communications ,0102 computer and information sciences ,02 engineering and technology ,Computational Complexity (cs.CC) ,01 natural sciences ,Industrial and Manufacturing Engineering ,Theoretical Computer Science ,APX-hardness ,Computer Science - Data Structures and Algorithms ,0202 electrical engineering, electronic engineering, information engineering ,NP-hardness ,Data Structures and Algorithms (cs.DS) ,Business and International Management ,Approximation Algorithm ,Temporal Graph ,Applied Mathematics ,Independent Set ,Temporal Line Graph ,Fixed-parameter Tractability ,Computer Science - Computational Complexity ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,020201 artificial intelligence & image processing ,Link Stream ,Computer Science - Discrete Mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
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 Δ ∈ ℕ is given. The requirement that a vertex cannot be matched twice in any Δ-window models some necessary "recovery" period that needs to pass for an entity (vertex) after being paired up for some activity with another entity. We prove strong computational hardness results for Maximum Temporal Matching, even for elementary cases. To cope with this computational hardness, we mainly focus on fixed-parameter algorithms with respect to natural parameters, as well as on polynomial-time approximation algorithms., LIPIcs, Vol. 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pages 27:1-27:14
- Published
- 2020
16. Parameterized Algorithms for Matrix Completion with Radius Constraints
- Author
-
Koana, Tomohiro, Froese, Vincent, and Niedermeier, Rolf
- Subjects
FOS: Computer and information sciences ,consensus string problems ,Discrete Mathematics (cs.DM) ,fixed-parameter tractability ,Closest String ,F.2.2 ,Computer Science - Discrete Mathematics ,Closest String with Wildcards - Abstract
Considering matrices with missing entries, we study NP-hard matrix completion problems where the resulting completed matrix should have limited (local) radius. In the pure radius version, this means that the goal is to fill in the entries such that there exists a "center string" which has Hamming distance to all matrix rows as small as possible. In stringology, this problem is also known as Closest String with Wildcards. In the local radius version, the requested center string must be one of the rows of the completed matrix. Hermelin and Rozenberg [CPM 2014, TCS 2016] performed a parameterized complexity analysis for Closest String with Wildcards. We answer one of their open questions, fix a bug concerning a fixed-parameter tractability result in their work, and improve some running time upper bounds. For the local radius case, we reveal a computational complexity dichotomy. In general, our results indicate that, although being NP-hard as well, this variant often allows for faster (fixed-parameter) algorithms., LIPIcs, Vol. 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020), pages 20:1-20:14
- Published
- 2020
- Full Text
- View/download PDF
17. Error Compensation in Leaf Power Problems
- Author
-
Dom, Michael, Guo, Jiong, Huffner, Falk, and Niedermeier, Rolf
- Published
- 2006
- Full Text
- View/download PDF
18. Isolation concepts applied to temporal clique enumeration.
- Author
-
Molter, Hendrik, Niedermeier, Rolf, and Renken, Malte
- Subjects
SUBGRAPHS ,SOCIAL network analysis ,CLIQUES (Sociology) - Abstract
Isolation is a concept originally conceived in the context of clique enumeration in static networks, mostly used to model communities that do not have much contact to the outside world. Herein, a clique is considered isolated if it has few edges connecting it to the rest of the graph. Motivated by recent work on enumerating cliques in temporal networks, we transform the isolation concept to the temporal setting. We discover that the addition of the time dimension leads to six distinct natural isolation concepts. Our main contribution is the development of parameterized enumeration algorithms for five of these six isolation types for clique enumeration, employing the parameter "degree of isolation." In a nutshell, this means that the more isolated these cliques are, the faster we can find them. On the empirical side, we implemented and tested these algorithms on (temporal) social network data, obtaining encouraging results. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
19. High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming.
- Author
-
BREDERECK, ROBERT, KACZMARCZYK, ANDRZEJ, KNOP, DUŠAN, and NIEDERMEIER, ROLF
- Subjects
COMPUTATIONAL complexity ,ALGORITHMS ,COMBINATORICS ,SOCIAL problems ,ECONOMIC equilibrium - Abstract
We study the (parameterized) computational complexity of problems in the context of fair allocations of indivisible goods. More specifically, we show fixed-parameter tractability results for a broad set of problems concerned with envy-free, Pareto-efficient allocations of items (with agent-specific utility functions) to agents. In principle, this implies efficient exact algorithms for these in general computationally intractable problems whenever we face instances with few agents and low maximum (absolute) utility values. This holds true also in high-multiplicity settings where we may have high numbers of identical items. On the technical side, our approach provides algorithmic meta-theorems covering a rich set of fair allocation problems in the additive preferences model. To achieve this, our main technical contribution is to make an elaborate use of tools from integer linear programming. More specifically, we exploit results originally going back to a famous theorem of Lenstra [Math. Oper. Res. 1983] concerning (the fixed-parameter tractability of) Integer Linear Programs (ILPs) with bounded dimension (that is, the dimension shall be considered as a (small) parameter) and the more recent framework of (combinatorial) N-fold ILPs. We reveal and exploit a fruitful interaction between these two cornerstones in the theory of integer linear programming, which may be of independent interest in applications going beyond fair allocations. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
20. Polynomial-Time Data Reduction for DOMINATING SET.
- Author
-
Alber, Jochen, Fellows, Michael R., and Niedermeier, Rolf
- Subjects
NP-complete problems ,COMPUTATIONAL complexity ,GRAPH theory ,DATA reduction ,TOPOLOGY ,COMBINATORIAL optimization ,MATHEMATICAL optimization - Abstract
Dealing with the NP-complete DOMINATING SET problem on graphs, we demonstrate the power of data reduction by preprocessing from a theoretical as well as a practical side. In particular, we prove that DOMINATING SET restricted to planar graphs has a so-called problem kernel of linear size, achieved by two simple and easy-to-implement reduction rules. Moreover, having implemented our reduction rules, first experiments indicate the impressive practical potential of these rules. Thus, this work seems to open up a new and prospective way how to cope with one of the most important problems in graph theory and combinatorial optimization. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
21. Reflections on Multivariate Algorithmics and Problem Parameterization
- Author
-
Niedermeier, Rolf, Institut für Informatik, Friedrich-Schiller-Universität = Friedrich Schiller University Jena [Jena, Germany], Inria Nancy Grand Est & Loria, Jean-Yves Marion and Thomas Schwentick, and Loria, Publications
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,Fixed-Parameter Tractability ,000 Computer science, knowledge, general works ,Algorithms and Complexity ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Parameterized Algorithmics ,Coping with Computational Intractability ,010201 computation theory & mathematics ,Computer Science ,0202 electrical engineering, electronic engineering, information engineering ,[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] ,020201 artificial intelligence & image processing - Abstract
International audience; Research on parameterized algorithmics for NP-hard problems has steadily grown over the last years. We survey and discuss how parameterized complexity analysis naturally develops into the field of multivariate algorithmics. Correspondingly, we describe how to perform a systematic investigation and exploitation of the “parameter space” of computationally hard problems.
- Published
- 2010
- Full Text
- View/download PDF
22. Computing maximum matchings in temporal graphs.
- Author
-
Mertzios, George B., Molter, Hendrik, Niedermeier, Rolf, Zamaraev, Viktor, and Zschoche, Philipp
- Subjects
- *
APPROXIMATION algorithms , *BIPARTITE graphs - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
23. A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack.
- Author
-
Bevern, René, Niedermeier, Rolf, and Suchý, Ondřej
- Subjects
COMPUTATIONAL complexity ,PRODUCTION scheduling ,MACHINE learning ,NP-hard problems ,POLYNOMIAL time algorithms - Abstract
We study the problem of non-preemptively scheduling n jobs, each job j with a release time $$t_j$$ , a deadline $$d_j$$ , and a processing time $$p_j$$ , on m parallel identical machines. Cieliebak et al. (2004) considered the two constraints $$|d_j-t_j|\le \lambda {}p_j$$ and $$|d_j-t_j|\le p_j +\sigma $$ and showed the problem to be NP-hard for any $$\lambda >1$$ and for any $$\sigma \ge 2$$ . We complement their results by parameterized complexity studies: we show that, for any $$\lambda >1$$ , the problem remains weakly NP-hard even for $$m=2$$ and strongly W[1]-hard parameterized by m. We present a pseudo-polynomial-time algorithm for constant m and $$\lambda $$ and a fixed-parameter tractability result for the parameter m combined with $$\sigma $$ . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
24. Co-Clustering under the Maximum Norm.
- Author
-
Bulteau, Laurent, Froese, Vincent, Hartung, Sepp, and Niedermeier, Rolf
- Subjects
CLUSTERING of particles ,PARALLEL algorithms ,BIOINFORMATICS ,HOMOGENEITY ,COMPUTATIONAL complexity - Abstract
Co-clustering, that is partitioning a numerical matrix into "homogeneous" submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting variants of co-clustering are NP-hard. We focus on the basic variant of co-clustering where the homogeneity of a submatrix is defined in terms of minimizing the maximum distance between two entries. In this context, we spot several NP-hard, as well as a number of relevant polynomial-time solvable special cases, thus charting the border of tractability for this challenging data clustering problem. For instance, we provide polynomial-time solvability when having to partition the rows and columns into two subsets each (meaning that one obtains four submatrices). When partitioning rows and columns into three subsets each, however, we encounter NP-hardness, even for input matrices containing only values from f0, 1, 2g. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
25. On finding separators in temporal split and permutation graphs.
- Author
-
Maack, Nicolas, Molter, Hendrik, Niedermeier, Rolf, and Renken, Malte
- Subjects
- *
PARAMETERIZATION , *NP-hard problems , *ISLANDS - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
26. The Parameterized Complexity of the Rainbow Subgraph Problem.
- Author
-
Hüffner, Falk, Komusiewicz, Christian, Niedermeier, Rolf, and Rötzschke, Martin
- Subjects
SUBGRAPHS ,GRAPH theory ,BIOINFORMATICS ,BIOMATHEMATICS ,ALGORITHMS - Abstract
The NP-hard RAINBOW SUBGRAPH problem, motivated from bioinformatics, is to find in an edge-colored graph a subgraph that contains each edge color exactly once and has at most k vertices. We examine the parameterized complexity of RAINBOW SUBGRAPH for paths, trees, and general graphs. We show that RAINBOW SUBGRAPH is W[1]-hard with respect to the parameter k and also with respect to the dual parameter ℓ := n - k where n is the number of vertices. Hence, we examine parameter combinations and show, for example, a polynomial-size problem kernel for the combined parameter ℓ and "maximum number of colors incident with any vertex". Additionally, we show APX-hardness even if the input graph is a properly edge-colored path in which every color occurs at most twice. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
27. POLYNOMIAL-TIME DATA REDUCTION FOR THE SUBSET INTERCONNECTION DESIGN PROBLEM.
- Author
-
JIEHUA CHEN, KOMUSIEWICZ, CHRISTIAN, NIEDERMEIER, ROLF, SORGE, MANUEL, SUCHý, ONDŘEJ, and WELLER, MATHIAS
- Subjects
BOREL subsets ,SUBGRAPHS ,GRAPH theory ,POLYNOMIALS ,SUBSET selection ,SET theory - Abstract
The NP-hard Subset Interconnection Design problem, also known as Minimum Topic-Connected Overlay, is motivated by numerous applications including the design of scalable overlay networks and vacuum systems. It has as input a finite set V and a collection of subsets V
1 , V2 , . . ., Vm ⊆ V, and asks for a minimum-cardinality edge set E such that for the graph G = (V,E) all induced subgraphs G[V1 ],G[V2 ], . . .,G[Vm ] are connected. We study Subset Interconnection Design in the context of polynomial-time data reduction rules that preserve the possibility of constructing optimal solutions. Our contribution is threefold: First, we show the incorrectness of earlier polynomial-time data reduction rules. Second, we show linear-time solvability in case of a constant number m of subsets, implying fixed-parameter tractability for the parameter m. Third, we provide a fixed-parameter tractability result for small subset sizes and tree-like output graphs. To achieve our results, we elaborate on polynomial-time data reduction rules which also may be of practical use in solving Subset Interconnection Design. [ABSTRACT FROM AUTHOR]- Published
- 2015
- Full Text
- View/download PDF
28. Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage.
- Author
-
Huffner, Falk, Komusiewicz, Christian, Liebtrau, Adrian, and Niedermeier, Rolf
- Abstract
A popular clustering algorithm for biological networks which was proposed by Hartuv and Shamir refid="ref5"/ identifies nonoverlapping highly connected components. We extend the approach taken by this algorithm by introducing the combinatorial optimization problem Highly Connected Deletion, which asks for removing as few edges as possible from a graph such that the resulting graph consists of highly connected components. We show that Highly Connected Deletion is NP-hard and provide a fixed-parameter algorithm and a kernelization. We propose exact and heuristic solution strategies, based on polynomial-time data reduction rules and integer linear programming with column generation. The data reduction typically identifies 75 percent of the edges that are deleted for an optimal solution; the column generation method can then optimally solve protein interaction networks with up to 6,000 vertices and 13,500 edges within five hours. Additionally, we present a new heuristic that finds more clusters than the method by Hartuv and Shamir. [ABSTRACT FROM PUBLISHER]
- Published
- 2014
- Full Text
- View/download PDF
29. EFFICIENT ALGORITHMS FOR EULERIAN EXTENSION AND RURAL POSTMAN.
- Author
-
DORN, FREDERIC, MOSER, HANNES, NIEDERMEIER, ROLF, and WELLER, MATHIAS
- Subjects
EULERIAN graphs ,ROUTING (Computer network management) ,MULTIGRAPH ,GRAPH theory ,LETTER carriers ,CHINESE people - Abstract
The aim of directed Eulerian extension problems is to make a given directed, possibly arc-weighted, (multi-)graph Eulerian by adding a minimum-cost set of arcs. These problems have natural applications in scheduling and arc routing and are closely related to the Chinese Postman and Rural Postman problems. Our main result is to show that the NP-hard Weighted Multigraph Eulerian Extension problem is fixed-parameter tractable with respect to the number k of extension arcs. For a directed n-vertex multigraph, the corresponding running time amounts to O(4
k ·n³). This also implies a fixed-parameter tractability result for the "equivalent" Rural Postman problem parameterized above guarantee. In addition, we present several polynomial-time algorithms for natural Eulerian extension problems, including undirected variants which can be defined analogously to the directed ones. [ABSTRACT FROM AUTHOR]- Published
- 2013
- Full Text
- View/download PDF
30. Approximation and Tidying-A Problem Kernel for s-Plex Cluster Vertex Deletion.
- Author
-
Bevern, René, Moser, Hannes, and Niedermeier, Rolf
- Subjects
APPROXIMATION theory ,POLYNOMIALS ,DATA reduction ,KERNEL functions ,GRAPHIC methods ,OUTLIERS (Statistics) - Abstract
We introduce the NP-hard graph-based data clustering problem s- Plex Cluster Vertex Deletion, where the task is to delete at most k vertices from a graph so that the connected components of the resulting graph are s-plexes. In an s-plex, every vertex has an edge to all but at most s−1 other vertices; cliques are 1-plexes. We propose a new method based on 'approximation and tidying' for kernelizing vertex deletion problems whose goal graphs can be characterized by forbidden induced subgraphs. The method exploits polynomial-time approximation results and thus provides a useful link between approximation and kernelization. Employing 'approximation and tidying', we develop data reduction rules that, in O( ksn) time, transform an s- Plex Cluster Vertex Deletion instance with n vertices into an equivalent instance with O( k s) vertices, yielding a problem kernel. To this end, we also show how to exploit structural properties of the specific problem in order to significantly improve the running time of the proposed kernelization method. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
31. Graph-based data clustering with overlaps.
- Author
-
Fellows, Michael R., Guo, Jiong, Komusiewicz, Christian, Niedermeier, Rolf, and Uhlmann, Johannes
- Subjects
GRAPH theory ,CLUSTER analysis (Statistics) ,COMPUTATIONAL complexity ,COMPUTER science ,MODIFICATIONS ,EXTREMAL problems (Mathematics) - Abstract
Abstract: We introduce overlap cluster graph modification problems where, other than in most previous works, the clusters of the target graph may overlap. More precisely, the studied graph problems ask for a minimum number of edge modifications such that the resulting graph consists of clusters (that is, maximal cliques) that may overlap up to a certain amount specified by the overlap number . In the case of -vertex-overlap, each vertex may be part of at most maximal cliques; -edge-overlap is analogously defined in terms of edges. We provide a complexity dichotomy (polynomial-time solvable versus NP-hard) for the underlying edge modification problems, develop forbidden subgraph characterizations of “cluster graphs with overlaps”, and study the parameterized complexity in terms of the number of allowed edge modifications, achieving fixed-parameter tractability (in case of constant -values) and parameterized hardness (in case of unbounded -values). [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
32. A MORE RELAXED MODEL FOR GRAPH-BASED DATA CLUSTERING: s-PLEX CLUSTER EDITING.
- Author
-
JIONG GUO, KOMUSIEWICZ, CHRISTIAN, NIEDERMEIER, ROLF, and UHLMANN, JOHANNES
- Subjects
GRAPH theory ,CLUSTER analysis (Statistics) ,NP-complete problems ,MATHEMATICAL transformations ,PATHS & cycles in graph theory ,KERNEL functions ,DATA reduction - Abstract
We introduce the S-PLEX CLUSTER EDITING problem as a generalization of the well-studied CLUSTER EDITING problem; both are NP-hard and both are motivated by graph-based data clustering. Instead of transforming a given graph by a minimum number of edge modifications into a disjoint union of cliques (this is CLUSTER EDITING), the task in the case of S-PLEX CLUSTER EDITING is to transform a graph into a cluster graph consisting of a disjoint union of so-called s-plexes. Herein, an s-plex is a vertex set S inducing a subgraph in which every vertex has degree at least |S| -- s. Cliques are 1-plexes. The advantage of s-plexes for s ≥ 2 is that they allow us to model a more relaxed cluster notion (s-plexes instead of cliques), better reflecting inaccuracies of the input data. We develop a provably effective preprocessing based on data reduction (yielding a so-called problem kernel), a forbidden subgraph characterization of s-plex cluster graphs, and a depth-bounded search tree which is used to find optimal edge modification sets. Altogether, this yields efficient algorithms in case of moderate numbers of edge modifications; this is often a reasonable assumption under a maximum parsimony model for data clustering. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
33. Fixed-parameter tractability results for feedback set problems in tournaments.
- Author
-
Dom, Michael, Guo, Jiong, Hüffner, Falk, Niedermeier, Rolf, and Truss, Anke
- Subjects
FEEDBACK control systems ,COMPUTATIONAL complexity ,POLYNOMIALS ,BIPARTITE graphs ,ITERATIVE methods (Mathematics) ,ALGORITHMS ,GAME theory - Abstract
Abstract: Complementing recent progress on classical complexity and polynomial-time approximability of feedback set problems in (bipartite) tournaments, we extend and improve fixed-parameter tractability results for these problems. We show that Feedback Vertex Set in tournaments (FVST) is amenable to the novel iterative compression technique, and we provide a depth-bounded search tree for Feedback Arc Set in bipartite tournaments based on a new forbidden subgraph characterization. Moreover, we apply the iterative compression technique to d-Hitting Set, which generalizes Feedback Vertex Set in tournaments, and obtain improved upper bounds for the time needed to solve 4-Hitting Set and 5-Hitting Set. Using our parameterized algorithm for Feedback Vertex Set in tournaments, we also give an exact (not parameterized) algorithm for it running in time, where n is the number of input graph vertices, answering a question of Woeginger [G.J. Woeginger, Open problems around exact algorithms, Discrete Appl. Math. 156 (3) (2008) 397–405]. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
34. Exact algorithms and applications for Tree-like Weighted Set Cover.
- Author
-
Guo, Jiong and Niedermeier, Rolf
- Subjects
NP-complete problems ,COMPUTATIONAL complexity ,GRAPH theory ,BIOINFORMATICS - Abstract
Abstract: We introduce an NP-complete special case of the Weighted Set Cover problem and show its fixed-parameter tractability with respect to the maximum subset size, a parameter that appears to be small in relevant applications. More precisely, in this practically relevant variant we require that the given collection C of subsets of a base set S should be “tree-like”. That is, the subsets in C can be organized in a tree T such that every subset one-to-one corresponds to a tree node and, for each element s of S, the nodes corresponding to the subsets containing s induce a subtree of T. This is equivalent to the problem of finding a minimum edge cover in an edge-weighted acyclic hypergraph. Our main result is an algorithm running in time where k denotes the maximum subset size, , and . The algorithm also implies a fixed-parameter tractability result for the NP-complete Multicut in Trees problem, complementing previous approximation results. Our results find applications in computational biology in phylogenomics and for saving memory in tree decomposition based graph algorithms. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
35. THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS.
- Author
-
WERNICKE, SEBASTIAN, ALBER, JOCHEN, GRAMM, JENS, GUO, JIONG, and NIEDERMEIER, ROLF
- Subjects
COMPUTATIONAL complexity ,NP-complete problems ,ERROR-correcting codes ,MEASUREMENT errors ,PARAMETER estimation ,POLYNOMIALS ,APPROXIMATION theory - Abstract
We initiate a systematic study of the ROW DELETION(B) problem on matrices: Given an input matrix A and a fixed "forbidden submatrix" B, the task is to remove a minimum number of rows from A such that no row or column permutation of B occurs as a submatrix in the resulting matrix. An application of this problem can be found, for instance, in the construction of perfect phylogenies. Establishing a strong connection to variants of the NP-complete HITTING SET problem, we describe and analyze structural properties of B that make ROW DELETION(B)NP-complete. On the positive side, the close relation with HITTING SET problems yields constant-factor polynomial-time approximation algorithms and fixed-parameter tractability results. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
36. An efficient fixed-parameter algorithm for 3-Hitting Set.
- Author
-
Niedermeier, Rolf and Rossmanith, Peter
- Subjects
COMPUTATIONAL biology ,NP-complete problems ,ALGORITHMS ,SET theory - Abstract
Given a collection
C of subsets of size three of a finite setS and a positive integerk , the 3-Hitting Set problem is to determine a subsetS′⊆S with&z.sfnc;S′&z.sfnc;⩽k , so thatS′ contains at least one element from each subset inC . The problem isNP -complete, and is motivated, for example, by applications in computational biology. Improving previous work, we give anO(2.270 time algorithm for 3-Hitting Set, which is efficient for small values ofk +n)k , a typical occurrence in some applications. Ford -Hitting Set we present anO(c time algorithm withk +n)c=d−1+O(d . [Copyright &y& Elsevier]−1 )- Published
- 2003
- Full Text
- View/download PDF
37. Feedback edge sets in temporal graphs.
- Author
-
Haag, Roman, Molter, Hendrik, Niedermeier, Rolf, and Renken, Malte
- Subjects
- *
EDGES (Geometry) , *NP-complete problems , *DYNAMIC programming - Abstract
The classical, linear-time solvable Feedback Edge Set problem is concerned with finding a minimum number of edges intersecting all cycles in a (static, unweighted) graph. We provide a first study of this problem in the setting of temporal graphs , where edges are present only at certain points in time. We find that there are four natural generalizations of Feedback Edge Set , all of which turn out to be NP-hard. We also study the tractability of these problems with respect to several parameters (solution size, lifetime, and number of graph vertices, among others) and obtain some parameterized hardness but also fixed-parameter tractability results. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
38. Temporal graph classes: A view through temporal separators.
- Author
-
Fluschnik, Till, Molter, Hendrik, Niedermeier, Rolf, Renken, Malte, and Zschoche, Philipp
- Subjects
- *
MOLECULAR graphs , *MACHINE separators , *COMPUTATIONAL complexity , *GEOMETRIC vertices , *DYNAMIC programming - Abstract
We investigate for temporal graphs the computational complexity of separating two distinct vertices s and z by vertex deletion. In a temporal graph, the vertex set is fixed but the edges have (discrete) time labels. Since the corresponding Temporal (s , z) -Separation problem is NP -complete, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph—there we observe polynomial-time solvability in the case of bounded treewidth—as well as restrictions concerning the "temporal evolution" along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
39. The parameterized complexity of the minimum shared edges problem.
- Author
-
Fluschnik, Till, Kratsch, Stefan, Niedermeier, Rolf, and Sorge, Manuel
- Subjects
- *
EDGES (Geometry) , *GEOMETRIC vertices - Abstract
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]
- Published
- 2019
- Full Text
- View/download PDF
40. Data reduction and exact algorithms for clique cover.
- Author
-
Gramm, Jens, Guo, Jiong, Hüffner, Falk, and Niedermeier, Rolf
- Abstract
To cover the edges of a graph with a minimum number of cliques is an NP-hard problem with many applications. For this problem we develop efficient and effective polynomial-time data reduction rules that, combined with a search tree algorithm, allow for exact problem solutions in competitive time. This is confirmed by experiments with real-world and synthetic data. Moreover, we prove the fixed-parameter tractability of covering edges by cliques. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
41. Exploiting hidden structure in selecting dimensions that distinguish vectors.
- Author
-
Froese, Vincent, van Bevern, René, Niedermeier, Rolf, and Sorge, Manuel
- Subjects
- *
VECTOR analysis , *NP-hard problems , *MATRICES (Mathematics) , *SET theory , *HAMMING distance - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
42. On making directed graphs transitive
- Author
-
Weller, Mathias, Komusiewicz, Christian, Niedermeier, Rolf, and Uhlmann, Johannes
- Subjects
- *
GRAPH theory , *MULTIPLY transitive groups , *DIRECTED graphs , *MULTILEVEL models , *NP-complete problems , *ALGORITHMS - Abstract
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]
- Published
- 2012
- Full Text
- View/download PDF
43. Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
- Author
-
Dom, Michael, Guo, Jiong, and Niedermeier, Rolf
- Subjects
- *
APPROXIMATION algorithms , *PARAMETER estimation , *MATRICES (Mathematics) , *POLYNOMIALS , *APPROXIMATION theory , *NUMERICAL analysis - Abstract
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]
- Published
- 2010
- Full Text
- View/download PDF
44. Parameterized computational complexity of Dodgson and Young elections
- Author
-
Betzler, Nadja, Guo, Jiong, and Niedermeier, Rolf
- Subjects
- *
COMPUTATIONAL complexity , *NP-complete problems , *ALGORITHMS , *ELECTIONS , *COMPLETENESS theorem , *SWITCHING theory , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2010
- Full Text
- View/download PDF
45. Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- Author
-
Alber, Jochen, Dorn, Frederic, and Niedermeier, Rolf
- Subjects
- *
MATHEMATICAL decomposition , *ALGORITHMS , *MATHEMATICS , *PROBABILITY theory - Abstract
Abstract: Many NP-complete problems on planar graphs are “fixed-parameter tractable:” Recent theoretical work provided tree decomposition-based fixed-parameter algorithms exactly solving various parameterized problems on planar graphs, among others VERTEX COVER, in time . Here, is some constant depending on the graph problem to be solved, is the number of graph vertices, and is the problem parameter (for VERTEX COVER this is the size of the vertex cover). In this paper, we present an experimental study for such tree decomposition-based algorithms focusing on VERTEX COVER. We demonstrate that the tree decomposition-based approach provides a valuable way of exactly solving VERTEX COVER on planar graphs. Doing so, we also demonstrate the impressive power of the so-called Nemhauser/Trotter theorem which provides a VERTEX COVER-specific, extremely useful data reduction through polynomial time preprocessing. Altogether, this underpins the practical importance of the underlying theory. [Copyright &y& Elsevier]
- Published
- 2005
- Full Text
- View/download PDF
46. Parameterized complexity: exponential speed-up for planar graph problems
- Author
-
Alber, Jochen, Fernau, Henning, and Niedermeier, Rolf
- Subjects
- *
GRAPH theory , *ALGORITHMS , *DEADLINES , *ALGEBRA - Abstract
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 instanceG of a problem on planar graphs with parameterk . 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]- Published
- 2004
- Full Text
- View/download PDF
47. Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters.
- Author
-
Bredereck, Robert, Heeger, Klaus, Knop, Dušan, and Niedermeier, Rolf
- Subjects
- *
BIPARTITE graphs , *LINEAR orderings , *ROOMMATES - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
48. The complexity of degree anonymization by vertex addition.
- Author
-
Bredereck, Robert, Froese, Vincent, Hartung, Sepp, Nichterlein, André, Niedermeier, Rolf, and Talmon, Nimrod
- Subjects
- *
COMPUTATIONAL complexity , *GRAPH theory , *PARAMETERIZATION , *MATHEMATICAL bounds , *NP-hard problems - Abstract
Motivated by applications in privacy-preserving data publishing, we study the problem of making an undirected graph k -anonymous by adding few vertices (together with some incident edges). That is, after adding these “dummy vertices”, for every vertex degree d appearing in the resulting graph, there shall be at least k vertices with degree d . We explore three variants of vertex addition (justified by real-world considerations) and study their (parameterized) computational complexity. We derive mostly intractability results, even for very restricted cases (including trees and bounded-degree graphs) but also obtain some encouraging fixed-parameter tractability results. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
49. Average parameterization and partial kernelization for computing medians
- Author
-
Betzler, Nadja, Guo, Jiong, Komusiewicz, Christian, and Niedermeier, Rolf
- Subjects
- *
COMPUTER algorithms , *DATA reduction , *PERMUTATIONS , *PARAMETERS (Statistics) , *COMPUTER science , *PARTIAL algebras - Abstract
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]
- Published
- 2011
- Full Text
- View/download PDF
50. Isolation concepts for clique enumeration: Comparison and computational experiments
- Author
-
Hüffner, Falk, Komusiewicz, Christian, Moser, Hannes, and Niedermeier, Rolf
- Subjects
- *
GRAPH theory , *MEASURE theory , *GRAPH connectivity , *NP-complete problems , *ALGORITHMS , *MATHEMATICAL models , *COMBINATORIAL enumeration problems - Abstract
Abstract: We do computational studies concerning the enumeration of isolated cliques in graphs. Isolation, as recently introduced, measures the degree of connectedness of the cliques to the rest of the graph. Isolation helps both in getting faster algorithms for the enumeration of maximal general cliques and in filtering out cliques with special semantics. We compare three isolation concepts and their combination with two enumeration modi for maximal cliques (“isolated maximal” vs “maximal isolated”). All studied concepts exhibit the fixed-parameter tractability of the enumeration task with respect to the parameter “degree of isolation”. We provide a first systematic experimental study of the corresponding enumeration algorithms, using synthetic graphs (in the model), financial networks, and a music artist similarity network, proposing the enumeration of isolated cliques as a useful instrument in analyzing financial and social networks. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.