TRIANGLE PACKINGIS an important NP-hard problem that has been well studied in exact and parameterized complexity. In this paper, we study kernelization of the PLANAR VERTEX-DISJOINT TRIANGLE PACKING problem, which is ...
详细信息
TRIANGLE PACKINGIS an important NP-hard problem that has been well studied in exact and parameterized complexity. In this paper, we study kernelization of the PLANAR VERTEX-DISJOINT TRIANGLE PACKING problem, which is to check whether a given planar graph has k vertex-disjoint triangles. We prove a kernel of 141k vertices, improving the previous bound of 732k. (C) 2022 Elsevier B.V. All rights reserved.
Branchwidth determines how graphs and, more generally, arbitrary connectivity (symmetric and submodular) functions can be decomposed into a tree-like structure by specific cuts. We develop a general framework for desi...
详细信息
Branchwidth determines how graphs and, more generally, arbitrary connectivity (symmetric and submodular) functions can be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing that either a sequence of particular refinement operations can decrease the width of a branch decomposition or the width of the decomposition is already within a factor of 2 from the optimum. The second ingredient is an efficient implementation of the refinement operations for branch decompositions that support efficient dynamic programming. We present two concrete applications of our general framework. The first is an algorithm that, for a given n-vertex graph C and integer k, in time 22O(k)n2 either constructs a rank decomposition of C of width at most 2k or concludes that the rankwidth of C is more than k. It also yields a (22k +1 - 1)approximation algorithm for cliquewidth within the same time complexity, which in turn improves to f (k) \cdot n2 the running times of various algorithms on graphs of cliquewidth k. Breaking the ``cubic barrier"" for rankwidth and cliquewidth was an open problem in the area. The second application is an algorithm that, for a given n-vertex graph C and integer k, in time 2O(k)n either constructs a branch decomposition of C of width at most 2k or concludes that the branchwidth of C is more than k. This improves over the 3-approximation that follows from the recent treewidth 2-approximation of Korhonen [FOCS 2021].
We provide simple, faster algorithms for the detection of cliques and dominating sets of fixed order. Our algorithms are based on reductions to rectangular matrix multiplication. We also describe an improved algorithm...
详细信息
We provide simple, faster algorithms for the detection of cliques and dominating sets of fixed order. Our algorithms are based on reductions to rectangular matrix multiplication. We also describe an improved algorithm for diamonds detection. (C) 2004 Elsevier B.V. All rights reserved.
We study the parameterized complexity of the Bounded-Degree Vertex Deletion problem (BDD), where the aim is to find a maximum induced subgraph whose maximum degree is below a given degree bound. Our focus lies on para...
详细信息
We study the parameterized complexity of the Bounded-Degree Vertex Deletion problem (BDD), where the aim is to find a maximum induced subgraph whose maximum degree is below a given degree bound. Our focus lies on parameters that measure the structural properties of the input instance. We first show that the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, treedepth, and even the size of a minimum vertex deletion set into graphs of pathwidth and treedepth at most three. We thereby resolve an open question stated in Betzler, Bredereck, Niedermeier and Uhlmann (2012) concerning the complexity of BDD parameterized by the feedback vertex set number. On the positive side, we obtain fixed-parameter algorithms for the problem with respect to the decompositional parameter treecut width and a novel problem-specific parameter called the core fracture number.
The notion of resolving sets in a graph was introduced by Slater [Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Util. Math., Winnipeg, 1975, pp. 549-559] and Harary an...
详细信息
The notion of resolving sets in a graph was introduced by Slater [Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Util. Math., Winnipeg, 1975, pp. 549-559] and Harary and Melter [Ars Combin., 2 (1976), pp. 191-195] as a way of uniquely identifying every vertex in a graph. A set of vertices in a graph is a resolving set if for any pair of vertices x and y there is a vertex in the set which has distinct distances to x and y. A smallest resolving set in a graph is called a metric basis and its size, the metric dimension of the graph. The problem of computing the metric dimension of a graph is a well-known NP-hard problem and while it was known to be polynomial time solvable on trees, it is only recently that efforts have been made to understand its computational complexity on various restricted graph classes. In recent work, Foucaud [Algorithmica, 2016, pp. 1-31] showed that this problem is NP-complete even on interval graphs. They complemented this result by also showing that it is fixed-parameter tractable (FPT) parameterized by the metric dimension of the graph. In this work, we show that this FPT result can in fact be extended to all graphs of bounded tree-length. This includes well-known classes like chordal graphs, AT-free graphs, and permutation graphs. We also show that this problem is FPT parameterized by the modular-width of the input graph.
We consider the following problem (and variants thereof) that has important applications in the construction and evaluation of phylogenetic trees: Two rooted unordered binary trees with the same number of leaves have ...
详细信息
We consider the following problem (and variants thereof) that has important applications in the construction and evaluation of phylogenetic trees: Two rooted unordered binary trees with the same number of leaves have to be embedded in two layers in the plane such that the leaves are aligned in two adjacent layers. Additional matching edges between the leaves give a one-to-one correspondence between pairs of leaves of the different trees. Our goal is to find two planar embeddings of the two trees (drawn without crossings) that minimize the number of crossings of the matching edges. We derive both (classical) complexity results and (parameterized) algorithms for this problem (and some variants thereof).(1) (C) 2009 Elsevier Inc. All rights reserved.
Visualization algorithms can have a large number of parameters, making the space of possible rendering results rather high-dimensional. Only a systematic analysis of the perceived quality can truly reveal the optimal ...
详细信息
Visualization algorithms can have a large number of parameters, making the space of possible rendering results rather high-dimensional. Only a systematic analysis of the perceived quality can truly reveal the optimal setting for each such parameter. However, an exhaustive search in which all possible parameter permutations are presented to each user within a study group would be infeasible to conduct. Additional complications may result from possible parameter co-dependencies. Here, we will introduce an efficient user study design and analysis strategy that is geared to cope with this problem. The user feedback is fast and easy to obtain and does not require exhaustive parameter testing. To enable such a framework we have modified a preference measuring methodology, conjoint analysis, that originated in psychology and is now also widely used in market research. We demonstrate our framework by a study that measures the perceived quality in volume rendering within the context of large parameter spaces.
We introduce a supporting combinatorial framework for the Flat Wall Theorem. In particular, we suggest two variants of the theorem and we introduce a new, more versatile, concept of wall homogeneity as well as the not...
详细信息
We introduce a supporting combinatorial framework for the Flat Wall Theorem. In particular, we suggest two variants of the theorem and we introduce a new, more versatile, concept of wall homogeneity as well as the notion of regularity in flat walls. All proposed concepts and results aim at facilitating the use of the irrelevant vertex technique in future algorithmic applications.
Let g, be a class of graphs. A graph G has g-width k if there are k independent sets N-1,...,N-k in G such that G can be embedded into a graph H is an element of g, such that for every edge e in H which is not an edge...
详细信息
Let g, be a class of graphs. A graph G has g-width k if there are k independent sets N-1,...,N-k in G such that G can be embedded into a graph H is an element of g, such that for every edge e in H which is not an edge in G, there exists an i such that both endvertices of e are in N-i. For the class B of block graphs we show that graphs with B-width at most 4 are perfect. We also show that B-width is NP-complete and show that it is fixed-parameter tractable. For the class C. of complete graphs, similar results are also obtained. (C) 2010 Elsevier B.V. All rights reserved.
In an undirected graph, a proper (k, i)-coloring is an assignment of a set of k colors to each vertex such that any two adjacent vertices have at most i common colors. The (k, i)-coloring problem is to compute the min...
详细信息
In an undirected graph, a proper (k, i)-coloring is an assignment of a set of k colors to each vertex such that any two adjacent vertices have at most i common colors. The (k, i)-coloring problem is to compute the minimum number of colors required for a proper (k, i)-coloring. This is a generalization of the classical graph coloring problem. We design a parameterized algorithm for the (k, i)-coloring problem with the size of the feedback vertex set as a parameter. Our algorithm does not use tree-width machinery, thus answering a question of Majumdar, Neogi, Raman and Tale [CALDAM 2017]. We also give a faster exact algorithm for (k, k - 1)-coloring. From the hardness perspective, we show that the (k, i)-coloring problem is NP-complete for any fixed values i, k, whenever i < k, thereby settling a conjecture of Mendez-Diaz and Zabala (1999) and again asked by Majumdar, Neogi, Raman and Tale. The NP-completeness result improves the partial NP-completeness shown in the preliminary version of this paper published in CALDAM 2018. (C) 2020 Elsevier B.V. All rights reserved.
暂无评论