On the proper intervalization of colored caterpillar trees

Carme Àlvarez; Maria Serna

RAIRO - Theoretical Informatics and Applications (2009)

  • Volume: 43, Issue: 4, page 667-686
  • ISSN: 0988-3754

Abstract

top
This paper studies the computational complexity of the proper interval colored graph problem (PICG), when the input graph is a colored caterpillar, parameterized by hair length. In order prove our result we establish a close relationship between the PICG and a graph layout problem the proper colored layout problem (PCLP). We show a dichotomy: the PICG and the PCLP are NP-complete for colored caterpillars of hair length ≥2, while both problems are in P for colored caterpillars of hair length <2. For the hardness results we provide a reduction from the multiprocessor scheduling problem, while the polynomial time results follow from a characterization in terms of forbidden subgraphs.

How to cite

top

Àlvarez, Carme, and Serna, Maria. "On the proper intervalization of colored caterpillar trees." RAIRO - Theoretical Informatics and Applications 43.4 (2009): 667-686. <http://eudml.org/doc/250603>.

@article{Àlvarez2009,
abstract = { This paper studies the computational complexity of the proper interval colored graph problem (PICG), when the input graph is a colored caterpillar, parameterized by hair length. In order prove our result we establish a close relationship between the PICG and a graph layout problem the proper colored layout problem (PCLP). We show a dichotomy: the PICG and the PCLP are NP-complete for colored caterpillars of hair length ≥2, while both problems are in P for colored caterpillars of hair length <2. For the hardness results we provide a reduction from the multiprocessor scheduling problem, while the polynomial time results follow from a characterization in terms of forbidden subgraphs. },
author = {Àlvarez, Carme, Serna, Maria},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Complexity; caterpillar tree; graph layout problems; coloring; complexity},
language = {eng},
month = {7},
number = {4},
pages = {667-686},
publisher = {EDP Sciences},
title = {On the proper intervalization of colored caterpillar trees},
url = {http://eudml.org/doc/250603},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Àlvarez, Carme
AU - Serna, Maria
TI - On the proper intervalization of colored caterpillar trees
JO - RAIRO - Theoretical Informatics and Applications
DA - 2009/7//
PB - EDP Sciences
VL - 43
IS - 4
SP - 667
EP - 686
AB - This paper studies the computational complexity of the proper interval colored graph problem (PICG), when the input graph is a colored caterpillar, parameterized by hair length. In order prove our result we establish a close relationship between the PICG and a graph layout problem the proper colored layout problem (PCLP). We show a dichotomy: the PICG and the PCLP are NP-complete for colored caterpillars of hair length ≥2, while both problems are in P for colored caterpillars of hair length <2. For the hardness results we provide a reduction from the multiprocessor scheduling problem, while the polynomial time results follow from a characterization in terms of forbidden subgraphs.
LA - eng
KW - Complexity; caterpillar tree; graph layout problems; coloring; complexity
UR - http://eudml.org/doc/250603
ER -

References

top
  1. C. Àlvarez, J. Díaz and M. Serna, The hardness of intervalizing four colored caterpillars. Discrete Math.235 (2001) 19–27.  
  2. C. Àlvarez, J. Díaz and M. Serna, Intervalizing colored graphs is NP-complete for caterpillars with hair length 2. Technical Report LSI 98-9-R, Universitat Politècnica de Catalunya (1998).  
  3. H. Bodlaender, M.R. Fellows and M.T. Hallet, Beyond NP-completeness for problems of bounded width: hardness for the W-hierarchy, in 26th ACM Symposium on Theory of Computing (1994) 449–458.  
  4. J. Díaz, A.M. Gibbons, M.S. Paterson and J. Torán, The minsumcut problem, in Algorithms and Datastructure, edited by F. Dehen, R.J. Sack and N. Santoro. Lect. Notes Comput. Sci.519 (1991) 65–79.  
  5. M.J. Dinneen, VLSI Layouts and DNA physical mappings. Technical Report, Los Alamos National Laboratory (1996).  
  6. M.R. Fellows, M.T. Hallet and W.T. Wareham, DNA physical mapping: Three ways difficult, in Algorithms-ESA'93, edited by T. Lengauer. Lect. Notes Comput. Sci.726 (1993) 157–168.  
  7. P.W. Goldberg, M.C. Golumbic, H. Kaplan and R. Shamir, Four strikes against physical mapping of DNA. J. Comput. Biol.2 (1995) 139–152.  
  8. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979).  
  9. M.C. Golumbic, H. Kaplan and R. Shamir, On the complexity of DNA physical mapping. Adv. Appl. Math.15 (1994) 203–215.  
  10. M.C. Golumbic, H. Kaplan and R. Shamir, Graph sandwich problems. J. Algorithms19 (1995) 449–473.  
  11. M.C. Golumbic, Algorithmic graph theory and perfect graphs. Academic Press, New York (1980).  
  12. M.C. Golumbic and R. Shamir, Complexity and algorithms for reasoning about time: A graph theoretical approach. J. ACM40 (1993) 1108–1113.  
  13. D. Kuo and G.J. Chang, The profile minimization problem in trees. SIAM J. Comput.23 (1994) 71–81.  
  14. H. Kaplan and R. Shamir, Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques. SIAM J. Comput.25 (1996) 540–561.  
  15. H. Kaplan, R. Shamir and R.E. Tarjan, Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput.28 (1999) 1906-1922.  
  16. B. Monien, The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Algebr. Discrete Methods7 (1986) 505–512.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.