Relevant bibliographies by topics / Parameterized complexity algorithms

Academic literature on the topic 'Parameterized complexity algorithms'

Author: Grafiati
Published: 7 July 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Parameterized complexity algorithms.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers

Journal articles on the topic "Parameterized complexity algorithms":

1

Marx, D. "Parameterized Complexity and Approximation Algorithms." Computer Journal 51, no. 1 (March 6, 2007): 60–78. http://dx.doi.org/10.1093/comjnl/bxm048.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Dabrowski, Konrad K., Peter Jonsson, Sebastian Ordyniak, and George Osipov. "Resolving Inconsistencies in Simple Temporal Problems: A Parameterized Approach." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 4 (June 28, 2022): 3724–32. http://dx.doi.org/10.1609/aaai.v36i4.20286.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
The simple temporal problem (STP) is one of the most influential reasoning formalisms for representing temporal information in AI. We study the problem of resolving inconsistency of data encoded in the STP. We prove that the problem of identifying a maximally large consistent subset of data is NP-hard. In practical instances, it is reasonable to assume that the amount of erroneous data is small. We therefore parameterize by the number of constraints that need to be removed to achieve consistency. Using tools from parameterized complexity we design fixed-parameter tractable algorithms for two large fragments of the STP. Our main algorithmic results employ reductions to the Directed Subset Feedback Arc Set problem and iterative compression combined with an efficient algorithm for the Edge Multicut problem. We complement our algorithmic results with hardness results that rule out fixed-parameter tractable algorithms for all remaining non-trivial fragments of the STP (under standard complexity-theoretic assumptions). Together, our results give a full classification of the classical and parameterized complexity of the problem.
3

Liu, Yunlong, Jianxin Wang, Jiong Guo, and Jianer Chen. "Complexity and parameterized algorithms for Cograph Editing." Theoretical Computer Science 461 (November 2012): 45–54. http://dx.doi.org/10.1016/j.tcs.2011.11.040.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Gasarch, W., and K. M. Kin. "Invitation to Fixed-Parameter Algorithms * Parameterized Complexity Theory * Parameterized Algorithmics: Theory, Practice and Prospects." Computer Journal 51, no. 1 (March 6, 2007): 137–40. http://dx.doi.org/10.1093/comjnl/bxm047.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Bulteau, Laurent, and Mathias Weller. "Parameterized Algorithms in Bioinformatics: An Overview." Algorithms 12, no. 12 (December 1, 2019): 256. http://dx.doi.org/10.3390/a12120256.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
Bioinformatics regularly poses new challenges to algorithm engineers and theoretical computer scientists. This work surveys recent developments of parameterized algorithms and complexity for important NP-hard problems in bioinformatics. We cover sequence assembly and analysis, genome comparison and completion, and haplotyping and phylogenetics. Aside from reporting the state of the art, we give challenges and open problems for each topic.
6

Kellerhals, Leon, Tomohiro Koana, Pascal Kunz, and Rolf Niedermeier. "Parameterized Algorithms for Colored Clustering." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 4 (June 26, 2023): 4400–4408. http://dx.doi.org/10.1609/aaai.v37i4.25560.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
In the Colored Clustering problem, one is asked to cluster edge-colored (hyper-)graphs whose colors represent interaction types. More specifically, the goal is to select as many edges as possible without choosing two edges that share an endpoint and are colored differently. Equivalently, the goal can also be described as assigning colors to the vertices in a way that fits the edge-coloring as well as possible. As this problem is NP-hard, we build on previous work by studying its parameterized complexity. We give a 2ᴼ⁽ᵏ⁾·nᴼ⁽¹⁾-time algorithm where k is the number of edges to be selected and n the number of vertices. We also prove the existence of a problem kernel of size O(k⁵ᐟ²), resolving an open problem posed in the literature. We consider parameters that are smaller than k, the number of edges to be selected, and r, the number of edges that can be deleted. Such smaller parameters are obtained by considering the difference between k or r and some lower bound on these values. We give both algorithms and lower bounds for Colored Clustering with such parameterizations. Finally, we settle the parameterized complexity of Colored Clustering with respect to structural graph parameters by showing that it is W[1]-hard with respect to both vertex cover number and tree-cut width, but fixed-parameter tractable with respect to local feedback edge number.
7

Blažej, Václav, Robert Ganian, Dušan Knop, Jan Pokorný, Šimon Schierreich, and Kirill Simonov. "The Parameterized Complexity of Network Microaggregation." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 5 (June 26, 2023): 6262–70. http://dx.doi.org/10.1609/aaai.v37i5.25771.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameterizations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network.
8

Fichte, Johannes K., Markus Hecher, and Arne Meier. "Counting Complexity for Reasoning in Abstract Argumentation." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 2827–34. http://dx.doi.org/10.1609/aaai.v33i01.33012827.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
In this paper, we consider counting and projected model counting of extensions in abstract argumentation for various semantics. When asking for projected counts we are interested in counting the number of extensions of a given argumentation framework while multiple extensions that are identical when restricted to the projected arguments count as only one projected extension. We establish classical complexity results and parameterized complexity results when the problems are parameterized by treewidth of the undirected argumentation graph. To obtain upper bounds for counting projected extensions, we introduce novel algorithms that exploit small treewidth of the undirected argumentation graph of the input instance by dynamic programming (DP). Our algorithms run in time double or triple exponential in the treewidth depending on the considered semantics. Finally, we take the exponential time hypothesis (ETH) into account and establish lower bounds of bounded treewidth algorithms for counting extensions and projected extension.
9

Eiben, Eduard, Robert Ganian, Thekla Hamm, and Viktoriia Korchemna. "A Structural Complexity Analysis of Synchronous Dynamical Systems." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 5 (June 26, 2023): 6313–21. http://dx.doi.org/10.1609/aaai.v37i5.25777.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
Synchronous dynamical systems are well-established models that have been used to capture a range of phenomena in networks, including opinion diffusion, spread of disease and product adoption. We study the three most notable problems in synchronous dynamical systems: whether the system will transition to a target configuration from a starting configuration, whether the system will reach convergence from a starting configuration, and whether the system is guaranteed to converge from every possible starting configuration. While all three problems were known to be intractable in the classical sense, we initiate the study of their exact boundaries of tractability from the perspective of structural parameters of the network by making use of the more fine-grained parameterized complexity paradigm. As our first result, we consider treewidth - as the most prominent and ubiquitous structural parameter - and show that all three problems remain intractable even on instances of constant treewidth. We complement this negative finding with fixed-parameter algorithms for the former two problems parameterized by treedepth, a well-studied restriction of treewidth. While it is possible to rule out a similar algorithm for convergence guarantee under treedepth, we conclude with a fixed-parameter algorithm for this last problem when parameterized by treedepth and the maximum in-degree.
10

Feldmann, Andreas Emil, Karthik C. Karthik C. S., Euiwoong Lee, and Pasin Manurangsi. "A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms." Algorithms 13, no. 6 (June 19, 2020): 146. http://dx.doi.org/10.3390/a13060146.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.
More sources
You might also be interested in the extended bibliographies on the topic 'Parameterized complexity algorithms' for particular source types:
Journal articles Dissertations / Theses Books

Dissertations / Theses on the topic "Parameterized complexity algorithms":

1

Xia, Ge. "Parameterized algorithms and computational lower bounds: a structural approach." Texas A&M University, 2005. http://hdl.handle.net/1969.1/4322.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
Many problems of practical significance are known to be NP-hard, and hence, are unlikely to be solved by polynomial-time algorithms. There are several ways to cope with the NP-hardness of a certain problem. The most popular approaches include heuristic algorithms, approximation algorithms, and randomized algorithms. Recently, parameterized computation and complexity have been receiving a lot of attention. By taking advantage of small or moderate parameter values, parameterized algorithms provide new venues for practically solving problems that are theoretically intractable. In this dissertation, we design efficient parameterized algorithms for several wellknown NP-hard problems and prove strong lower bounds for some others. In doing so, we place emphasis on the development of new techniques that take advantage of the structural properties of the problems. We present a simple parameterized algorithm for Vertex Cover that uses polynomial space and runs in time O(1.2738k + kn). It improves both the previous O(1.286k + kn)-time polynomial-space algorithm by Chen, Kanj, and Jia, and the very recent O(1.2745kk4 + kn)-time exponential-space algorithm, by Chandran and Grandoni. This algorithm stands out for both its performance and its simplicity. Essential to the design of this algorithm are several new techniques that use structural information of the underlying graph to bound the search space. For Vertex Cover on graphs with degree bounded by three, we present a still better algorithm that runs in time O(1.194k + kn), based on an “almost-global” analysis of the search tree. We also show that an important structural property of the underlying graphs – the graph genus – largely dictates the computational complexity of some important graph problems including Vertex Cover, Independent Set and Dominating Set. We present a set of new techniques that allows us to prove almost tight computational lower bounds for some NP-hard problems, such as Clique, Dominating Set, Hitting Set, Set Cover, and Independent Set. The techniques are further extended to derive computational lower bounds on polynomial time approximation schemes for certain NP-hard problems. Our results illustrate a new approach to proving strong computational lower bounds for some NP-hard problems under reasonable conditions.
2

Kim, Eun Jung. "Parameterized algorithms on digraph and constraint satisfaction problems." Thesis, Royal Holloway, University of London, 2010. http://repository.royalholloway.ac.uk/items/4e3a1971-6e98-97a9-8e4f-9e1fdc76066a/9/.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
While polynomial-time approximation algorithms remain a dominant notion in tackling computationally hard problems, the framework of parameterized complexity has been emerging rapidly in recent years. Roughly speaking, the analytic framework of parameterized complexity attempts to grasp the difference between problems which admit O(c^k . poly(n))-time algorithms such as Vertex Cover, and problems like Dominating Set for which essentially brute-force O(n^k)-algorithms are best possible until now. Problems of the former type is said to be fixed-parameter tractable (FPT) and those of the latter type are regarded intractable. In this thesis, we investigate some problems on directed graphs and a number of constraint satisfaction problems (CSPs) from the parameterized perspective. We develop fixed-parameter algorithms for some digraph problems. In particular, we focus on the basic problem of finding a tree with certain property embedded in a given digraph. New or improved fpt-algorthms are presented for finding an out-branching with many or few leaves (Directed Maximum Leaf, Directed Minimum Leaf problems). For acyclic digraphs, Directed Maximum Leaf is shown to allow a kernel with linear number of vertices. We suggest a kernel for Directed Minimum Leaf with quadratic number of vertices. An improved fpt-algorithm for finding k-Out-Tree is presented and this algorithm is incorporated as a subroutine to obtain a better algorithm for Directed Minimum Leaf. In the second part of this thesis, we concentrate on several CSPs in which we want to maximize the number of satisfied constraints and consider parameterization "above tight lower bound" for these problems. To deal with this type of parameterization, we present a new method called SABEM using probabilistic approach and applying harmonic analysis on pseudo-boolean functions. Using SABEM we show that a number of CSPs admit polynomial kernels, thus being fixed-parameter tractable. Moreover, we suggest some problem-specific combinatorial approaches to Max-2-Sat and a wide special class of Max-Lin2, which lead to a kernel of smaller size than what can be obtained using SABEM for respective problems.
3

Enciso, Rosa. "Alliances in Graphs: Parameterized Algorithms and on Partitioning Series-Parallel Graphs." Doctoral diss., University of Central Florida, 2009. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/2479.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
Alliances are used to denote agreements between members of a group with similar interests. Alliances can occur between nations, biological sequences, business cartels, and other entities. The notion of alliances in graphs was first introduced by Kristiansen, Hedetniemi, and Hedetniemi in . A defensive alliance in a graph G=(V,E) is a non empty set S⊆V S where, for all x ∈S, |N∩S|≥|N-S|. Consequently, every vertex that is a member of a defensive alliance has at least as many vertices defending it as there are vertices attacking it. Alliances can be used to model a variety of applications such as classification problems, communities in the web distributed protocols, etc . In , Gerber and Kobler introduced the problem of partitioning a graph into strong defensive alliances for the first time as the "Satisfactory Graph Partitioning (SGP)" problem. In his dissertation , Shafique used the problem of partitioning a graph into alliances to model problems in data clustering. Decision problems for several types of alliances and alliance partitions have been shown to be NP-complete. However, because of their applicability, it is of interest to study methods to overcome the complexity of these problems. In this thesis, we will present a variety of algorithms for finding alliances in different families of graphs with a running time that is polynomial in terms of the size of the input, and allowing exponential running time as a function of a chosen parameter. This study is guided by the theory of parameterized complexity introduced by Rod Downey and Michael Fellows in . In addition to parameterized algorithms for alliance related problems, we study the partition of series-parallel graphs into alliances. The class of series-parallel graphs is a special class in graph theory since many problems known to be NP-complete on general graphs have been shown to have polynomial time algorithms on series-parallel graphs. For example, the problem of finding a minimum defensive alliance has been shown to have a linear time algorithm when restricted to series-parallel graphs . Series-parallel graphs have also been to focus of study in a wide range of applications including CMOS layout and scheduling problems [ML86, Oud97]. Our motivation is driven by clustering properties that can be modeled with alliances. We observe that partitioning series-parallel graphs into alliances of roughly the same size can be used to partition task graphs to minimize the communication between processors and balance the workload of each processor. We present a characterization of series-parallel graphs that allow a partition into defensive alliances and a subclass of series-parallel graphs with a satisfactory partitions.
Ph.D.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Science PhD
4

Dinh, Hiep. "Exploring Algorithms for Branch Decompositions of Planar Graphs." Ohio University / OhioLINK, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1222984625.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Zhang, Fenghui. "Effective algorithms and protocols for wireless networking: a topological approach." Diss., Texas A&M University, 2008. http://hdl.handle.net/1969.1/86012.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
Much research has been done on wireless sensor networks. However, most protocols and algorithms for such networks are based on the ideal model Unit Disk Graph (UDG) model or do not assume any model. Furthermore, many results assume the knowledge of location information of the network. In practice, sensor networks often deviate from the UDG model significantly. It is not uncommon to observe stable long links that are more than five times longer than unstable short links in real wireless networks. A more general network model, the quasi unit-disk graph (quasi-UDG) model, captures much better the characteristics of wireless networks. However, the understanding of the properties of general quasi-UDGs has been very limited, which is impeding the design of key network protocols and algorithms. In this dissertation we study the properties for general wireless sensor networks and develop new topological/geometrical techniques for wireless sensor networking. We assume neither the ideal UDG model nor the location information of the nodes. Instead we work on the more general quasi-UDG model and focus on figuring out the relationship between the geometrical properties and the topological properties of wireless sensor networks. Based on such relationships we develop algorithms that can compute useful substructures (planar subnetworks, boundaries, etc.). We also present direct applications of the properties and substructures we constructed including routing, data storage, topology discovery, etc. We prove that wireless networks based on quasi-UDG model exhibit nice properties like separabilities, existences of constant stretch backbones, etc. We develop efficient algorithms that can obtain relatively dense planar subnetworks for wireless sensor networks. We also present efficient routing protocols and balanced data storage scheme that supports ranged queries. We present algorithmic results that can also be applied to other fields (e.g., information management). Based on divide and conquer and improved color coding technique, we develop algorithms for path, matching and packing problem that significantly improve previous best algorithms. We prove that it is unlikely for certain problems in operation science and information management to have any relatively effective algorithm or approximation algorithm for them.
6

Chan, Hubert. "A Parameterized Algorithm for Upward Planarity Testing of Biconnected Graphs." Thesis, University of Waterloo, 2003. http://hdl.handle.net/10012/1090.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
We can visualize a graph by producing a geometric representation of the graph in which each node is represented by a single point on the plane, and each edge is represented by a curve that connects its two endpoints. Directed graphs are often used to model hierarchical structures; in order to visualize the hierarchy represented by such a graph, it is desirable that a drawing of the graph reflects this hierarchy. This can be achieved by drawing all the edges in the graph such that they all point in an upwards direction. A graph that has a drawing in which all edges point in an upwards direction and in which no edges cross is known as an upward planar graph. Unfortunately, testing if a graph is upward planar is NP-complete. Parameterized complexity is a technique used to find efficient algorithms for hard problems, and in particular, NP-complete problems. The main idea is that the complexity of an algorithm can be constrained, for the most part, to a parameter that describes some aspect of the problem. If the parameter is fixed, the algorithm will run in polynomial time. In this thesis, we investigate contracting an edge in an upward planar graph that has a specified embedding, and show that we can determine whether or not the resulting embedding is upward planar given the orientation of the clockwise and counterclockwise neighbours of the given edge. Using this result, we then show that under certain conditions, we can join two upward planar graphs at a vertex and obtain a new upward planar graph. These two results expand on work done by Hutton and Lubiw. Finally, we show that a biconnected graph has at most k!8k-1 planar embeddings, where k is the number of triconnected components. By using an algorithm by Bertolazzi et al. that tests whether a given embedding is upward planar, we obtain a parameterized algorithm, where the parameter is the number of triconnected components, for testing the upward planarity of a biconnected graph. This algorithm runs in O(k!8kn3) time.
7

Cadena, Jose Eduardo. "Finding Interesting Subgraphs with Guarantees." Diss., Virginia Tech, 2018. http://hdl.handle.net/10919/81960.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
Networks are a mathematical abstraction of the interactions between a set of entities, with extensive applications in social science, epidemiology, bioinformatics, and cybersecurity, among others. There are many fundamental problems when analyzing network data, such as anomaly detection, dense subgraph mining, motif finding, information diffusion, and epidemic spread. A common underlying task in all these problems is finding an "interesting subgraph"; that is, finding a part of the graph---usually small relative to the whole---that optimizes a score function and has some property of interest, such as connectivity or a minimum density. Finding subgraphs that satisfy common constraints of interest, such as the ones above, is computationally hard in general, and state-of-the-art algorithms for many problems in network analysis are heuristic in nature. These methods are fast and usually easy to implement. However, they come with no theoretical guarantees on the quality of the solution, which makes it difficult to assess how the discovered subgraphs compare to an optimal solution, which in turn affects the data mining task at hand. For instance, in anomaly detection, solutions with low anomaly score lead to sub-optimal detection power. On the other end of the spectrum, there have been significant advances on approximation algorithms for these challenging graph problems in the theoretical computer science community. However, these algorithms tend to be slow, difficult to implement, and they do not scale to the large datasets that are common nowadays. The goal of this dissertation is developing scalable algorithms with theoretical guarantees for various network analysis problems, where the underlying task is to find subgraphs with constraints. We find interesting subgraphs with guarantees by adapting techniques from parameterized complexity, convex optimization, and submodularity optimization. These techniques are well-known in the algorithm design literature, but they lead to slow and impractical algorithms. One unifying theme in the problems that we study is that our methods are scalable without sacrificing the theoretical guarantees of these algorithm design techniques. We accomplish this combination of scalability and rigorous bounds by exploiting properties of the problems we are trying to optimize, decomposing or compressing the input graph to a manageable size, and parallelization. We consider problems on network analysis for both static and dynamic network models. And we illustrate the power of our methods in applications, such as public health, sensor data analysis, and event detection using social media data.
Ph. D.
8

Sau, Ignasi. "Optimization in Graphs under Degree Constraints. Application to Telecommunication Networks." Phd thesis, Université de Nice Sophia-Antipolis, 2009. http://tel.archives-ouvertes.fr/tel-00429092.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
La première partie de cette thèse s'intéresse au groupage de trafic dans les réseaux de télécommunications. La notion de groupage de trafic correspond à l'agrégation de flux de faible débit dans des conduits de plus gros débit. Cependant, à chaque insertion ou extraction de trafic sur une longueur d'onde il faut placer dans le noeud du réseau un multiplexeur à insertion/extraction (ADM). De plus il faut un ADM pour chaque longueur d'onde utilisée dans le noeud, ce qui représente un coût d'équipements important. Les objectifs du groupage de trafic sont d'une part le partage efficace de la bande passante et d'autre part la réduction du coût des équipements de routage. Nous présentons des résultats d'inapproximabilité, des algorithmes d'approximation, un nouveau modèle qui permet au réseau de pouvoir router n'importe quel graphe de requêtes de degré borné, ainsi que des solutions optimales pour deux scénarios avec trafic all-to-all: l'anneau bidirectionnel et l'anneau unidirectionnel avec un facteur de groupage qui change de manière dynamique. La deuxième partie de la thèse s'intéresse aux problèmes consistant à trouver des sous-graphes avec contraintes sur le degré. Cette classe de problèmes est plus générale que le groupage de trafic, qui est un cas particulier. Il s'agit de trouver des sous-graphes d'un graphe donné avec contraintes sur le degré, tout en optimisant un paramètre du graphe (très souvent, le nombre de sommets ou d'arêtes). Nous présentons des algorithmes d'approximation, des résultats d'inapproximabilité, des études sur la complexité paramétrique, des algorithmes exacts pour les graphes planaires, ainsi qu'une méthodologie générale qui permet de résoudre efficacement cette classe de problèmes (et de manière plus générale, la classe de problèmes tels qu'une solution peut être codé avec une partition d'un sous-ensemble des sommets) pour les graphes plongés dans une surface. Finalement, plusieurs annexes présentent des résultats sur des problèmes connexes.
9

Daligault, Jean. "Techniques combinatoires pour les algorithmes paramétrés et les noyaux, avec applications aux problèmes de multicoupe." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2011. http://tel.archives-ouvertes.fr/tel-00804206.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille k dans un graphe à n sommets peut être décidée en temps f(k) ∗ poly(n). Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en k. Nous donnons un algorithme en temps O∗(3.72k) pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que 2n). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les s−t numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées.
10

Chopin, Morgan. "Problèmes d'optimisation avec propagation dans les graphes : complexité paramétrée et approximation." Phd thesis, Université Paris Dauphine - Paris IX, 2013. http://tel.archives-ouvertes.fr/tel-00933769.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
Dans cette thèse, nous étudions la complexité algorithmique de problèmes d'optimisation impliquant un processus de diffusion dans un graphe. Plus précisément, nous nous intéressons tout d'abord au problème de sélection d'un ensemble cible. Ce problème consiste à trouver le plus petit ensemble de sommets d'un graphe à "activer" au départ tel que tous les autres sommets soient activés après un nombre fini d'étapes de propagation. Si nous modifions ce processus en permettant de "protéger" un sommet à chaque étape, nous obtenons le problème du pompier dont le but est de minimiser le nombre total de sommets activés en protégeant certains sommets. Dans ce travail, nous introduisons et étudions une version généralisée de ce problème dans laquelle plus d'un sommet peut être protégé à chaque étape. Nous proposons plusieurs résultats de complexité pour ces problèmes à la fois du point de vue de l'approximation mais également de la complexité paramétrée selon des paramètres standards ainsi que des paramètres liés à la structure du graphe.
More sources

Books on the topic "Parameterized complexity algorithms":

1

IWPEC 2004 (2004 Bergen, Norway). Parameterized and exact computation: First international workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004 : proceedings. Berlin: Springer, 2004.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

IWPEC 2008 (2008 Victoria, B.C.). Parameterized and exact computation: Third international workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008 : proceedings. Berlin: Springer, 2008.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Raman, V. Parameterized and Exact Computation: 5th International Symposium, IPEC 2010, Chennai, India, December 13-15, 2010. Proceedings. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Thilikos, Dimitrios M. Parameterized and Exact Computation: 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

IWPEC 2009 (2009 Copenhagen, Denmark). Parameterized and exact computation: 4th international workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009 : revised selected papers. Berlin: Springer, 2009.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Marx, Daniel. Parameterized and Exact Computation: 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

Parameterized Complexity Theory. Springer, 2010.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

Flum, J., and M. Grohe. Parameterized Complexity Theory. Springer, 2006.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

Rosamond, Frances, Neeldhara Misra, and Meirav Zehavi, eds. New Frontiers in Parameterized Complexity and Algorithms. MDPI, 2024. http://dx.doi.org/10.3390/books978-3-7258-1302-5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Flum, J., and M. Grohe. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer, 2006.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Parameterized complexity algorithms":

1

Golovach, Petr A., Marcin Kamiński, Spyridon Maniatis, and Dimitrios M. Thilikos. "The Parameterized Complexity of Graph Cyclability." In Algorithms - ESA 2014, 492–504. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014. http://dx.doi.org/10.1007/978-3-662-44777-2_41.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Bazgan, Cristina, Morgan Chopin, and Michael R. Fellows. "Parameterized Complexity of the Firefighter Problem." In Algorithms and Computation, 643–52. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-25591-5_66.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Cooper, Alexandre, Stephanie Maaz, Amer E. Mouawad, and Naomi Nishimura. "Parameterized Complexity of Reconfiguration of Atoms." In WALCOM: Algorithms and Computation, 263–74. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-030-96731-4_22.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Aravind, N. R., and Roopam Saxena. "Parameterized Complexity of Path Set Packing." In WALCOM: Algorithms and Computation, 291–302. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-27051-2_25.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Panolan, Fahad, and Saket Saurabh. "Matroids in Parameterized Complexity and Exact Algorithms." In Encyclopedia of Algorithms, 1203–6. New York, NY: Springer New York, 2016. http://dx.doi.org/10.1007/978-1-4939-2864-4_783.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Dörnfelder, Martin, Jiong Guo, Christian Komusiewicz, and Mathias Weller. "On the Parameterized Complexity of Consensus Clustering." In Algorithms and Computation, 624–33. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-25591-5_64.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Panolan, Fahad, and Saket Saurabh. "Matroids in Parameterized Complexity and Exact Algorithms." In Encyclopedia of Algorithms, 1–4. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015. http://dx.doi.org/10.1007/978-3-642-27848-8_783-1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Dey, Palash, Arnab Maiti, and Amatya Sharma. "On Parameterized Complexity of Liquid Democracy." In Algorithms and Discrete Applied Mathematics, 83–94. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-67899-9_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Liu, Yunlong, Jianxin Wang, Jiong Guo, and Jianer Chen. "Cograph Editing: Complexity and Parameterized Algorithms." In Lecture Notes in Computer Science, 110–21. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-22685-4_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Agrawal, Akanksha, Pratibha Choudhary, N. S. Narayanaswamy, K. K. Nisha, and Vijayaragunathan Ramamoorthi. "Parameterized Complexity of Minimum Membership Dominating Set." In WALCOM: Algorithms and Computation, 288–99. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-030-96731-4_24.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Parameterized complexity algorithms":

1

Neumann, Frank, and Andrew M. Sutton. "Parameterized Complexity Analysis of Evolutionary Algorithms." In GECCO '15: Genetic and Evolutionary Computation Conference. New York, NY, USA: ACM, 2015. http://dx.doi.org/10.1145/2739482.2756562.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Neumann, Frank, and Andrew M. Sutton. "Parameterized complexity analysis of evolutionary algorithms." In GECCO '14: Genetic and Evolutionary Computation Conference. New York, NY, USA: ACM, 2014. http://dx.doi.org/10.1145/2598394.2605351.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Lin, Bingkai. "The Parameterized Complexity of k-Biclique." In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2014. http://dx.doi.org/10.1137/1.9781611973730.41.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Maiti, Arnab, and Palash Dey. "Parameterized Algorithms for Kidney Exchange." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. California: International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/58.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
In kidney exchange programs, multiple patient-donor pairs each of whom are otherwise incompatible, exchange their donors to receive compatible kidneys. The Kidney Exchange problem is typically modelled as a directed graph where every vertex is either an altruistic donor or a pair of patient and donor; directed edges are added from a donor to its compatible patients. The computational task is to find if there exists a collection of disjoint cycles and paths starting from altruistic donor vertices of length at most l_c and l_p respectively that covers at least some specific number t of non-altruistic vertices (patients). We study parameterized algorithms for the kidney exchange problem in this paper. Specifically, we design FPT algorithms parameterized by each of the following parameters: (1) the number of patients who receive kidney, (2) treewidth of the input graph + max{l_p, l_c}, and (3) the number of vertex types in the input graph when l_p <= l_c. We also present interesting algorithmic and hardness results on the kernelization complexity of the problem. Finally, we present an approximation algorithm for an important special case of Kidney Exchange.
5

Deligkas, Argyrios, Eduard Eiben, Robert Ganian, Thekla Hamm, and Sebastian Ordyniak. "The Parameterized Complexity of Connected Fair Division." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/20.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
We study the Connected Fair Division problem (CFD), which generalizes the fundamental problem of fairly allocating resources to agents by requiring that the items allocated to each agent form a connected subgraph in a provided item graph G. We expand on previous results by providing a comprehensive complexity-theoretic understanding of CFD based on several new algorithms and lower bounds while taking into account several well-established notions of fairness: proportionality, envy-freeness, EF1 and EFX. In particular, we show that to achieve tractability, one needs to restrict both the agents and the item graph in a meaningful way. We design (XP)-algorithms for the problem parameterized by (1) clique-width of G plus the number of agents and (2) treewidth of G plus the number of agent types, along with corresponding lower bounds. Finally, we show that to achieve fixed-parameter tractability, one needs to not only use a more restrictive parameterization of G, but also include the maximum item valuation as an additional parameter.
6

Grüttemeier, Niels, Christian Komusiewicz, and Nils Morawietz. "On the Parameterized Complexity of Polytree Learning." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/580.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
A Bayesian network is a directed acyclic graph that represents statistical dependencies between variables of a joint probability distribution. A fundamental task in data science is to learn a Bayesian network from observed data. Polytree Learning is the problem of learning an optimal Bayesian network that fulfills the additional property that its underlying undirected graph is a forest. In this work, we revisit the complexity of Polytree Learning. We show that Polytree Learning can be solved in single-exponential FPT time for the number of variables. Moreover, we consider the influence of d, the number of variables that might receive a nonempty parent set in the final DAG on the complexity of Polytree Learning. We show that Polytree Learning is presumably not fixed-parameter tractable for d, unlike Bayesian network learning which is fixed-parameter tractable for d. Finally, we show that if d and the maximum parent set size are bounded, then we can obtain efficient algorithms.
7

Deligkas, Argyrios, Eduard Eiben, and Tiger-Lily Goldsmith. "Parameterized Complexity of Hotelling-Downs with Party Nominees." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. California: International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/35.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
We study a generalization of the Hotelling-Downs model through the lens of parameterized complexity. In this model, there is a set of voters on a line and a set of parties that compete over them. Each party has to choose a nominee from a set of candidates with predetermined positions on the line, where each candidate comes at a different cost. The goal of every party is to choose the most profitable nominee, given the nominees chosen by the rest of the parties; the profit of a party is the number of voters closer to their nominee minus its cost. We examine the complexity of deciding whether a pure Nash equilibrium exists for this model under several natural parameters: the number of different positions of the candidates, the discrepancy and the span of the nominees, and the overlap of the parties. We provide FPT and XP algorithms and we complement them with a W[1]-hardness result.
8

Silva, Janio Carlos Nascimento, Uéverton dos Santos Souza, and Luiz Satoru Ochi. "Algorithmic Aspects of Problems Related to Optimization, Circuits, and Parameterized Complexity." In Concurso de Teses e Dissertações. Sociedade Brasileira de Computação - SBC, 2022. http://dx.doi.org/10.5753/ctd.2022.223305.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
This thesis investigates several aspects of computational problems related to circuits and neighborhood exploration. Supported by a vast literature, we explore notable trends in algorithms, optimization, and computational complexity; and we provide some results for each topic discussed. The thesis' contributions are organized into four projects: (i) the study of SUCCINCT MONOTONE CIRCUIT CERTIFICATION (SMCC); (ii) the study of BEST-CASE ENERGY COMPLEXITY IN SATISFYING ASSIGNMENTS (MINEC+M); (iii) the proposition of the Th-hierarchy as an alternative to the hierarchy of complexity classes so-called W-hierarchy; and (iv) the study of the MAXIMUM MULTI IMPROVEMENT problem. Over the course of these four projects, we develop polynomial and parameterized reductions, NP-completeness proofs, classical and parameterized complexity analysis, and implementations of exact algorithms and metaheuristics.
9

Bliznets, Ivan, Marek Cygan, Pawel Komosa, Lukáš Mach, and Michał Pilipczuk. "Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems." In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2015. http://dx.doi.org/10.1137/1.9781611974331.ch79.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Arrighi, Emmanuel, Henning Fernau, Daniel Lokshtanov, Mateus de Oliveira Oliveira, and Petra Wolf. "Diversity in Kemeny Rank Aggregation: A Parameterized Approach." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
In its most traditional setting, the main concern of optimization theory is the search for optimal solutions for instances of a given computational problem. A recent trend of research in artificial intelligence, called solution diversity, has focused on the development of notions of optimality that may be more appropriate in settings where subjectivity is essential. The idea is that instead of aiming at the development of algorithms that output a single optimal solution, the goal is to investigate algorithms that output a small set of sufficiently good solutions that are sufficiently diverse from one another. In this way, the user has the opportunity to choose the solution that is most appropriate to the context at hand. It also displays the richness of the solution space. When combined with techniques from parameterized complexity theory, the paradigm of diversity of solutions offers a powerful algorithmic framework to address problems of practical relevance. In this work, we investigate the impact of this combination in the field of Kemeny Rank Aggregation, a well-studied class of problems lying in the intersection of order theory and social choice theory and also in the field of order theory itself. In particular, we show that KRA is fixed-parameter tractable with respect to natural parameters providing natural formalizations of the notions of diversity and of the notion of a sufficiently good solution. Our main results work both when considering the traditional setting of aggregation over linearly ordered votes, and in the more general setting where votes are partially ordered.

To the bibliography