Document Open Access Logo

Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity

Authors Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2016.20.pdf
  • Filesize: 0.92 MB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • orientation
  • graph class
  • width parameter
  • parameterized complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

The problem Max W-Light (Max W-Heavy) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, Max 0-Light is equivalent to the problem of finding a maximum independent set.

In this paper, we show that for any fixed constant W, Max W-Heavy can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width.

To have a polynomial-time algorithm for Max W-Light, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin, Todinca, and Villanger [SIAM J. Comput., 44(1):57-87, 2015]. The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too.

We also study the parameterized complexity of the problems and show some tractability and intractability results.

Cite As Get BibTex

Hans L. Bodlaender, Hirotaka Ono, and Yota Otachi. Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.20

Author Details

Hans L. Bodlaender
Hirotaka Ono
Yota Otachi

References

  1. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. J. Algorithms, 12:308-340, 1991. URL: http://dx.doi.org/10.1016/0196-6774(91)90006-K.
  2. Yuichi Asahiro, Jesper Jansson, Eiji Miyano, and Hirotaka Ono. Upper and lower degree bounded graph orientation with minimum penalty. In CATS, volume 128 of CRPIT, pages 139-146, 2012. URL: http://crpit.com/abstracts/CRPITV128Asahiro.html.
  3. Yuichi Asahiro, Jesper Jansson, Eiji Miyano, and Hirotaka Ono. Graph orientations optimizing the number of light or heavy vertices. Journal of Graph Algorithms and Applications, 19:441-465, 2015. URL: http://dx.doi.org/10.7155/jgaa.00371.
  4. Yuichi Asahiro, Jesper Jansson, Eiji Miyano, and Hirotaka Ono. Degree-constrained graph orientation: Maximum satisfaction and minimum violation. Theory Comput. Syst., 58:60-93, 2016. URL: http://dx.doi.org/10.1007/s00224-014-9565-5.
  5. Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono, and Kouhei Zenmyo. Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree. J. Comb. Optim., 22:78-96, 2011. URL: http://dx.doi.org/10.1007/s10878-009-9276-z.
  6. Hans L. Bodlaender, Pinar Heggernes, and Jan Arne Telle. Recognizability equals definability for graphs of bounded treewidth and bounded chordality. Electronic Notes in Discrete Mathematics, 49:559-568, 2015. URL: http://dx.doi.org/10.1016/j.endm.2015.06.076.
  7. Hans L. Bodlaender, Ton Kloks, Dieter Kratsch, and Haiko Müller. Treewidth and minimum fill-in on d-trapezoid graphs. J. Graph Algorithms Appl., 2:1-23, 1998. URL: http://dx.doi.org/10.7155/jgaa.00008.
  8. Vincent Bouchitté and Ioan Todinca. Listing all potential maximal cliques of a graph. Theor. Comput. Sci., 276:17-32, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00007-X.
  9. Marek Chrobak and David Eppstein. Planar orientations with low out-degree and compaction of adjacency matrices. Theor. Comput. Sci., 86:243-266, 1991. URL: http://dx.doi.org/10.1016/0304-3975(91)90020-3.
  10. Fan R. K. Chung, Michael R. Garey, and Robert E. Tarjan. Strongly connected orientations of mixed multigraphs. Networks, 15:477-484, 1985. URL: http://dx.doi.org/10.1002/net.3230150409.
  11. Derek G. Corneil and Udi Rotics. On the relationship between clique-width and treewidth. SIAM J. Comput., 34:825-847, 2005. URL: http://dx.doi.org/10.1137/S0097539701385351.
  12. Bruno Courcelle. The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues. Theor. Inform. Appl., 26:257-286, 1992. Google Scholar
  13. Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101:77-114, 2000. URL: http://dx.doi.org/10.1016/S0166-218X(99)00184-5.
  14. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  15. Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider. Clique-width is NP-complete. SIAM J. Discrete Math., 23:909-939, 2009. URL: http://dx.doi.org/10.1137/070687256.
  16. Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and CMSO. SIAM J. Comput., 44:54-87, 2015. URL: http://dx.doi.org/10.1137/140964801.
  17. A. Frank and A. Gyárfás. How to orient the edges of a graph? In Combinatorics, volume 18 of Colloq. Math. Soc. Janos Bolyai, pages 353-364, 1978. Google Scholar
  18. Harold N. Gabow. Upper degree-constrained partial orientations. In SODA 2006, pages 554-563, 2006. Google Scholar
  19. Frank Gurski and Egon Wanke. The tree-width of clique-width bounded graphs without K_n,n. In WG 2000, volume 1928 of LNCS, pages 196-205, 2000. URL: http://dx.doi.org/10.1007/3-540-40064-8_19.
  20. Michel Habib and Rolf H. Möhring. Treewidth of cocomparability graphs and a new order-theoretic parameter. Order, 11:47-60, 1994. URL: http://dx.doi.org/10.1007/BF01462229.
  21. S. Louis Hakimi. On the degrees of the vertices of a directed graph. Journal of the Franklin Institute, 279:290-308, 1965. URL: http://dx.doi.org/10.1016/0016-0032(65)90340-6.
  22. Pinar Heggernes. Treewidth, partial k-trees, and chordal graphs. Partial curriculum in INF334 - Advanced algorithmical techniques, University of Bergen, Norway, 2005. URL: http://www.ii.uib.no/~pinar/chordal.pdf.
  23. Kaveh Khoshkhah. On finding orientations with the fewest number of vertices with small out-degree. Discrete Applied Mathematics, 194:163-166, 2015. URL: http://dx.doi.org/10.1016/j.dam.2015.05.007.
  24. Subhash Khot and Venkatesh Raman. Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci., 289:997-1008, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00414-5.
  25. Ton Kloks and Dieter Kratsch. Treewidth of chordal bipartite graphs. J. Algorithms, 19:266-281, 1995. URL: http://dx.doi.org/10.1006/jagm.1995.1037.
  26. Ton Kloks, Dieter Kratsch, and C. K. Wong. Minimum fill-in on circle and circular-arc graphs. J. Algorithms, 28:272-289, 1998. URL: http://dx.doi.org/10.1006/jagm.1998.0936.
  27. Ton Kloks, Ching-Hao Liu, and Sheung-Hung Poon. Feedback vertex set on chordal bipartite graphs. CoRR, abs/1104.3915, 2011. URL: http://arxiv.org/abs/1104.3915.
  28. Dieter Kratsch. The Structure of Graphs and the Design of Efficient Algorithms. Habilitation thesis, Friedrich-Schiller-University of Jena, Germany, 1996. Google Scholar
  29. H. G. Landau. On dominance relations and the structure of animal societies: III The condition for a score structure. Bulletin of Mathematical Biology, 15:143-148, 1953. URL: http://dx.doi.org/10.1007/BF02476378.
  30. C. G. Lekkerkerker and J. Ch. Boland. Representation of a finite graph by a set of intervals on the real line. Fund. Math., 51:45-64, 1962. URL: http://eudml.org/doc/213681.
  31. Luke Mathieson. The parameterized complexity of editing graphs for bounded degeneracy. Theor. Comput. Sci., 411:3181-3187, 2010. URL: http://dx.doi.org/10.1016/j.tcs.2010.05.015.
  32. David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. J. ACM, 30:417-427, 1983. URL: http://dx.doi.org/10.1145/2402.322385.
  33. C. St. J. A. Nash-Williams. On orientations, connectivity and odd vertex pairings in finite graphs. Canad. J. Math, 12:555-567, 1960. URL: http://dx.doi.org/10.4153/CJM-1960-049-6.
  34. Sang-il Oum. Approximating rank-width and clique-width quickly. ACM Transactions on Algorithms, 5, 2008. Article No. 10. URL: http://dx.doi.org/10.1145/1435375.1435385.
  35. Sang-il Oum and Paul D. Seymour. Approximating clique-width and branch-width. J. Comb. Theory, Ser. B, 96:514-528, 2006. URL: http://dx.doi.org/10.1016/j.jctb.2005.10.006.
  36. Marcin Pilipczuk and Michal Pilipczuk. Finding a maximum induced degenerate subgraph faster than 2ⁿ. In IPEC 2012, volume 7535 of LNCS, pages 3-12, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33293-7_3.
  37. H. E. Robbins. A theorem on graphs, with an application to a problem of traffic control. American Mathematical Monthly, 46:281-283, 1939. URL: http://dx.doi.org/10.2307/2303897.
  38. Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science &Business Media, 2003. Google Scholar
  39. Richard P. Stanley. Acyclic orientations of graphs. Discrete Mathematics, 5:171-178, 1973. URL: http://dx.doi.org/10.1016/0012-365X(73)90108-8.
  40. Venkat Venkateswaran. Minimizing maximum indegree. Discrete Applied Mathematics, 143:374-378, 2004. URL: http://dx.doi.org/10.1016/j.dam.2003.07.007.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact