Document Open Access Logo

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

Authors Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

PDF
Thumbnail PDF

File

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

Document Identifiers

Author Details

Hans L. Bodlaender
Hirotaka Ono
Yota Otachi

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

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.

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

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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact