Abstract
A (k,r)-tuple is a word of length r on an alphabet of size k. A graph is (k,r)-representable if we can assign a (k,r)-tuple to each vertex such that two vertices are connected iff the associated tuples agree on some component. We study the complexity of several graph problems on (k,r)-representable graphs, as a function of the parameters k,r; the problems under study are Maximum Independent Set, Minimum Dominating Set and Maximum Clique. In this framework, there are two classes of interest: the graphs representable with tuples of logarithmic length (i.e. graphs (k,r)-representable with r = O(k logn)), and the graphs representable with tuples of polynomial length (i.e. graphs (k,r)-representable with r = poly(n)). In both cases, we show that the problems are computationally hard, though we obtain stronger hardness results in the second case. Our hardness results also allow us to derive optimality results for Multidimensional Matching and Disjoint r -Subsets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alber, J., Bodlaender, H., Fernau, H., Niedermeier, R.: Fixed parameter algorithms for planar dominating set and related problems. In: Halldórsson, M.M. (ed.) SWAT 2000. LNCS, vol. 1851, pp. 97–110. Springer, Heidelberg (2000)
Alon, N., Yuster, R., Zwick, U.: Color-coding. Journal of the Association for Computing Machinery 42(4), 844–856 (1995)
Buss, J.F., Goldsmith, J.: Nondeterminism within P. SIAM Journal on Computing 22, 560–572 (1993)
Cai, L., Juedes, D.: On the existence of subexponential parameterized algorithms. Journal of Computer and System Sciences 67(4), 789–807 (2003)
Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D., Kanj, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Information and Computation 201(2), 216–231 (2005)
Dehne, F., Fellows, M., Rosamond, F.: An FPT algorithm for Set Splitting. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 180–191. Springer, Heidelberg (2003)
Dehne, F.K.H.A., Fellows, M.R., Langston, M.A., Rosamond, F.A., Stevens, K.: An O(2O(k) n 3) FPT Algorithm for the Undirected Feedback Vertex Set Problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 859–869. Springer, Heidelberg (2005)
Downey, R., Estivill, V., Fellows, M., Prieto, E., Rosamond, F.: Cutting up is hard to do: the parameterized complexity of k-cut and related problems. In: Proceedings of CATS 2003. ENTCS, vol. 78 (2003)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Fellows, M., Knauer, C., Nishimura, N., Ragde, P., Rosamonds, F., Stege, U., Thilikos, D., Whitesides, S.: Faster fixed-parameter tractable algorithms for matching and packing problems. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 311–322. Springer, Heidelberg (2004)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New-York (1979)
Mehlhorn, K.: Data Structures and Algorithms. Springer, Heidelberg (1990)
Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences 67(4), 757–771 (2003)
Welsh, D.J.A., Powell, M.B.: An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal 10, 85–86 (1967)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guillemot, S. (2006). Parameterized Problems on Coincidence Graphs. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_27
Download citation
DOI: https://doi.org/10.1007/11940128_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49694-6
Online ISBN: 978-3-540-49696-0
eBook Packages: Computer ScienceComputer Science (R0)