Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Graph Motif problem parameterized by the structure of the input graph
86
0
0.0
(
0
)
Added by
Florian Sikora
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The Graph Motif problem was introduced in 2006 in the context of biological networks. It consists of deciding whether or not a multiset of colors occurs in a connected subgraph of a vertex-colored graph. Graph Motif has been mostly analyzed from the standpoint of parameterized complexity. The main parameters which came into consideration were the size of the multiset and the number of colors. Though, in the many applications of Graph Motif, the input graph originates from real-life and has structure. Motivated by this prosaic observation, we systematically study its complexity relatively to graph structural parameters. For a wide range of parameters, we give new or improved FPT algorithms, or show that the problem remains intractable. For the FPT cases, we also give some kernelization lower bounds as well as some ETH-based lower bounds on the worst case running time. Interestingly, we establish that Graph Motif is W[1]-hard (while in W[P]) for parameter max leaf number, which is, to the best of our knowledge, the first problem to behave this way.
rate research
Read More
Given two graphs $G_1$ and $G_2$ on $n$ vertices each, we define a graph $G$ on vertex set $V_1times V_2$ and the edge set as the union of edges of $G_1times bar{G_2}$, $bar{G_1}times G_2$, ${(v,u),(v,u))(|u,uin V_2}$ for each $vin V_1$, and ${((u,v),(u,v))|u,uin V_1}$ for each $vin V_2$. We consider the completely-positive Lovasz $vartheta$ function, i.e., $cpvartheta$ function for $G$. We show that the function evaluates to $n$ whenever $G_1$ and $G_2$ are isomorphic and to less than $n-1/(4n^4)$ when non-isomorphic. Hence this function provides a test for graph isomorphism. We also provide some geometric insight into the feasible region of the completely positive program.
We consider the problems of deciding whether an input graph can be modified by removing/adding at most k vertices/edges such that the result of the modification satisfies some property definable in first-order logic. We establish a number of sufficient and necessary conditions on the quantification pattern of the first-order formula phi for the problem to be fixed-parameter tractable or to admit a polynomial kernel.
Graph-modification problems, where we add/delete a small number of vertices/edges to make the given graph to belong to a simpler graph class, is a well-studied optimization problem in all algorithmic paradigms including classical, approximation and parameterized complexity. Specifically, graph-deletion problems, where one needs to delete at most $k$ vertices to place it in a given non-trivial hereditary (closed under induced subgraphs) graph class, captures several well-studied problems including {sc Vertex Cover}, {sc Feedback Vertex Set}, {sc Odd Cycle Transveral}, {sc Cluster Vertex Deletion}, and {sc Perfect Deletion}. Investigation into these problems in parameterized complexity has given rise to powerful tools and techniques. While a precise characterization of the graph classes for which the problem is {it fixed-parameter tractable} (FPT) is elusive, it has long been known that if the graph class is characterized by a {it finite} set of forbidden graphs, then the problem is FPT. In this paper, we initiate a study of a natural variation of the problem of deletion to {it scattered graph classes} where we need to delete at most $k$ vertices so that in the resulting graph, each connected component belongs to one of a constant number of graph classes. A simple hitting set based approach is no longer feasible even if each of the graph classes is characterized by finite forbidden sets. As our main result, we show that this problem is fixed-parameter tractable (FPT) when the deletion problem corresponding to each of the finite classes is known to be FPT and the properties that a graph belongs to each of the classes is expressible in CMSO logic. When each graph class has a finite forbidden set, we give a faster FPT algorithm using the well-known techniques of iterative compression and important separators.
The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization that has been recently proposed is the $k$-anonymity. This approach requires that the rows of a table are partitioned in clusters of size at least $k$ and that all the rows in a cluster become the same tuple, after the suppression of some entries. The natural optimization problem, where the goal is to minimize the number of suppressed entries, is known to be APX-hard even when the records values are over a binary alphabet and $k=3$, and when the records have length at most 8 and $k=4$ . In this paper we study how the complexity of the problem is influenced by different parameters. In this paper we follow this direction of research, first showing that the problem is W[1]-hard when parameterized by the size of the solution (and the value $k$). Then we exhibit a fixed parameter algorithm, when the problem is parameterized by the size of the alphabet and the number of columns. Finally, we investigate the computational (and approximation) complexity of the $k$-anonymity problem, when restricting the instance to records having length bounded by 3 and $k=3$. We show that such a restriction is APX-hard.
We carry out a systematic study of a natural covering problem, used for identification across several areas, in the realm of parameterized complexity. In the {sc Test Cover} problem we are given a set $[n]={1,...,n}$ of items together with a collection, $cal T$, of distinct subsets of these items called tests. We assume that $cal T$ is a test cover, i.e., for each pair of items there is a test in $cal T$ containing exactly one of these items. The objective is to find a minimum size subcollection of $cal T$, which is still a test cover. The generic parameterized version of {sc Test Cover} is denoted by $p(k,n,|{cal T}|)$-{sc Test Cover}. Here, we are given $([n],cal{T})$ and a positive integer parameter $k$ as input and the objective is to decide whether there is a test cover of size at most $p(k,n,|{cal T}|)$. We study four parameterizations for {sc Test Cover} and obtain the following: (a) $k$-{sc Test Cover}, and $(n-k)$-{sc Test Cover} are fixed-parameter tractable (FPT). (b) $(|{cal T}|-k)$-{sc Test Cover} and $(log n+k)$-{sc Test Cover} are W[1]-hard. Thus, it is unlikely that these problems are FPT.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
