The Experts below are selected from a list of 15588 Experts worldwide ranked by ideXlab platform
Saket Saurabh - One of the best experts on this subject based on the ideXlab platform.
-
parameterized algorithms for max colorable Induced Subgraph problem on perfect graphs
Algorithmica, 2019Co-Authors: Neeldhara Misra, Venkatesh Raman, Saket Saurabh, Fahad PanolanAbstract:We address the parameterized complexity of Max Colorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable Induced Subgraph of an input graph G. Yannakakis and Gavril (Inf Process Lett 24:133–137, 1987) showed that this problem is NP-complete even on split graphs if q is part of input, but gave an $$n^{O(q)}$$ algorithm on chordal graphs. We first observe that the problem is W[2]-hard when parameterized by q, even on split graphs. However, when parameterized by $$\ell $$ , the number of vertices in the solution, we give two fixed-parameter tractable algorithms. The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. Finally, we show that (under standard complexity-theoretic assumption) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense:
-
parameterized algorithms for max colorable Induced Subgraph problem on perfect graphs
Workshop on Graph-Theoretic Concepts in Computer Science, 2013Co-Authors: Neeldhara Misra, Venkatesh Raman, Saket Saurabh, Fahad PanolanAbstract:We address the parameterized complexity of Max Colorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable Induced Subgraph of an input graph G. Yannakakis and Gavril [IPL 1987] showed that this problem is NP-complete even on split graphs if q is part of input, but gave a n O(q) algorithm on chordal graphs. We first observe that the problem is W[2]-hard parameterized by q, even on split graphs. However, when parameterized by l, the number of vertices in the solution, we give two fixed-parameter tractable algorithms.
-
maximum r regular Induced Subgraph problem fast exponential algorithms and combinatorial bounds
SIAM Journal on Discrete Mathematics, 2012Co-Authors: Sushmita Gupta, Venkatesh Raman, Saket SaurabhAbstract:We show that for a fixed $r$, the number of maximal $r$-regular Induced Subgraphs in any graph with $n$ vertices is upper bounded by $\mathcal{O}(c^n)$, where $c$ is a positive constant strictly less than $2$. This bound generalizes the well-known result of Moon and Moser, who showed an upper bound of $3^{n/3}$ on the number of maximal independent sets of a graph on $n$ vertices. We complement this upper bound result by obtaining an almost tight lower bound on the number of (possible) maximal $r$-regular Induced Subgraphs possible in a graph on $n$ vertices. Our upper bound results are algorithmic. That is, we can enumerate all the maximal $r$-regular Induced Subgraphs in time $\mathcal{O}(c^n n^{\mathcal{O}(1)})$. A related question is that of finding a maximum-sized $r$-regular Induced Subgraph. Given a graph $G=(V,E)$ on $n$ vertices, the Maximum $r$-Regular Induced Subgraph (M-$r$-RIS) problem asks for a maximum-sized subset of vertices, $R \subseteq V$, such that the Induced Subgraph on $R$ is $r$-re...
-
fast exponential algorithms for maximum γ regular Induced Subgraph problems
Foundations of Software Technology and Theoretical Computer Science, 2006Co-Authors: Sushmita Gupta, Venkatesh Raman, Saket SaurabhAbstract:Given a graph G = (V,E) on n vertices, the Maximum γ-Regular Induced Subgraph (M-γ-RIS) problems ask for a maximum sized subset of vertices R⊆V such that the Induced Subgraph on R, G[R], is γ-regular. We give an $\mathcal{O}(c^n)$ time algorithm for these problems for any fixed constant γ, where c is a positive constant strictly less than 2, solving a well known open problem. These algorithms are then generalized to solve counting and enumeration version of these problems in the same time. An interesting consequence of the enumeration algorithm is, that it shows that the number of maximal γ-regular Induced Subgraphs for a fixed constant γ on any graph on n vertices is upper bounded by o(2n). We then give combinatorial lower bounds on the number of maximal γ-regular Induced Subgraphs possible on a graph on n vertices and also give matching algorithmic upper bounds. We use the techniques and results obtained in the paper to obtain an improved exact algorithm for a special case of Induced Subgraph Isomorphism that is Induced γ-Regular Subgraph Isomorphism, where γ is a constant. All the algorithms in the paper are simple but their analyses are not. Some of the upper bound proofs or algorithms require a new and different measure than the usual number of vertices or edges to measure the progress of the algorithm, and require solving an interesting system of polynomials.
-
fast exponential algorithms for maximum r regular Induced Subgraph problems
Lecture Notes in Computer Science, 2006Co-Authors: Sushmita Gupta, Venkatesh Raman, Saket SaurabhAbstract:Given a graph G = (V, E) on n vertices, the MAXIMUM r-REGULAR Induced Subgraph (M-r-RIS) problems ask for a maximum sized subset of vertices R C V such that the Induced Subgraph on R, G[R], is r-regular. We give an O(c n ) time algorithm for these problems for any fixed constant r, where c is a positive constant strictly less than 2, solving a well known open problem. These algorithms are then generalized to solve counting and enumeration version of these problems in the same time. An interesting consequence of the enumeration algorithm is, that it shows that the number of maximal r-regular Induced Subgraphs for a fixed constant r on any graph on n vertices is upper bounded by o(2). We then give combinatorial lower bounds on the number of maximal r-regular Induced Subgraphs possible on a graph on n vertices and also give matching algorithmic upper bounds. We use the techniques and results obtained in the paper to obtain an improved exact algorithm for a special case of Induced SUB GRAPH ISOMORPHISM that is Induced r-REGULAR Subgraph ISOMORPHISM, where r is a constant. All the algorithms in the paper are simple but their analyses are not. Some of the upper bound proofs or algorithms require a new and different measure than the usual number of vertices or edges to measure the progress of the algorithm, and require solving an interesting system of polynomials.
Paul Seymour - One of the best experts on this subject based on the ideXlab platform.
-
Induced Subgraphs of graphs with large chromatic number iv consecutive holes
Journal of Combinatorial Theory Series B, 2018Co-Authors: Alex Scott, Paul SeymourAbstract:Abstract A hole in a graph is an Induced Subgraph which is a cycle of length at least four. We prove that for all ν > 0 , every triangle-free graph with sufficiently large chromatic number contains holes of ν consecutive lengths.
-
Induced Subgraphs of graphs with large chromatic number iv consecutive holes
arXiv: Combinatorics, 2015Co-Authors: Alex Scott, Paul SeymourAbstract:A hole in a graph is an Induced Subgraph which is a cycle of length at least four. We prove that for every positive integer k, every triangle-free graph with sufficiently large chromatic number contains holes of k consecutive lengths.
-
Induced Subgraphs of graphs with large chromatic number i odd holes
arXiv: Combinatorics, 2014Co-Authors: Alex Scott, Paul SeymourAbstract:An odd hole in a graph is an Induced Subgraph which is a cycle of odd length at least five. In 1985, A. Gyarfas made the conjecture that for all t there exists n such that every graph with no K_t Subgraph and no odd hole is n-colourable. We prove this conjecture.
-
the strong perfect graph theorem
Annals of Mathematics, 2006Co-Authors: Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin ThomasAbstract:A graph G is perfect if for every Induced Subgraph H, the chromatic number of H equals the size of the largest complete Subgraph of H, and G is Berge if no Induced Subgraph of G is an odd cycle of length at least five or the complement of one. The ?strong perfect graph conjecture? (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornu?ejols and Vuiskovi?c ? that every Berge graph either falls into one of a few basic classes, or admits one of a few kinds of separation (designed so that a minimum counterexample to Berge?s conjecture cannot have either of these properties). In this paper we prove both of these conjectures.
-
the strong perfect graph theorem
arXiv: Combinatorics, 2002Co-Authors: Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin ThomasAbstract:A graph G is perfect if for every Induced Subgraph H, the chromatic number of H equals the size of the largest complete Subgraph of H, and G is Berge if no Induced Subgraph of G is an odd cycle of length at least 5 or the complement of one. The "strong perfect graph conjecture" (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornuejols and Vuskovic -- that every Berge graph either falls into one of a few basic classes, or it has a kind of separation that cannot occur in a minimal imperfect graph. In this paper we prove both these conjectures.
Venkatesh Raman - One of the best experts on this subject based on the ideXlab platform.
-
parameterized algorithms for max colorable Induced Subgraph problem on perfect graphs
Algorithmica, 2019Co-Authors: Neeldhara Misra, Venkatesh Raman, Saket Saurabh, Fahad PanolanAbstract:We address the parameterized complexity of Max Colorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable Induced Subgraph of an input graph G. Yannakakis and Gavril (Inf Process Lett 24:133–137, 1987) showed that this problem is NP-complete even on split graphs if q is part of input, but gave an $$n^{O(q)}$$ algorithm on chordal graphs. We first observe that the problem is W[2]-hard when parameterized by q, even on split graphs. However, when parameterized by $$\ell $$ , the number of vertices in the solution, we give two fixed-parameter tractable algorithms. The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. Finally, we show that (under standard complexity-theoretic assumption) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense:
-
parameterized algorithms for max colorable Induced Subgraph problem on perfect graphs
Workshop on Graph-Theoretic Concepts in Computer Science, 2013Co-Authors: Neeldhara Misra, Venkatesh Raman, Saket Saurabh, Fahad PanolanAbstract:We address the parameterized complexity of Max Colorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable Induced Subgraph of an input graph G. Yannakakis and Gavril [IPL 1987] showed that this problem is NP-complete even on split graphs if q is part of input, but gave a n O(q) algorithm on chordal graphs. We first observe that the problem is W[2]-hard parameterized by q, even on split graphs. However, when parameterized by l, the number of vertices in the solution, we give two fixed-parameter tractable algorithms.
-
maximum r regular Induced Subgraph problem fast exponential algorithms and combinatorial bounds
SIAM Journal on Discrete Mathematics, 2012Co-Authors: Sushmita Gupta, Venkatesh Raman, Saket SaurabhAbstract:We show that for a fixed $r$, the number of maximal $r$-regular Induced Subgraphs in any graph with $n$ vertices is upper bounded by $\mathcal{O}(c^n)$, where $c$ is a positive constant strictly less than $2$. This bound generalizes the well-known result of Moon and Moser, who showed an upper bound of $3^{n/3}$ on the number of maximal independent sets of a graph on $n$ vertices. We complement this upper bound result by obtaining an almost tight lower bound on the number of (possible) maximal $r$-regular Induced Subgraphs possible in a graph on $n$ vertices. Our upper bound results are algorithmic. That is, we can enumerate all the maximal $r$-regular Induced Subgraphs in time $\mathcal{O}(c^n n^{\mathcal{O}(1)})$. A related question is that of finding a maximum-sized $r$-regular Induced Subgraph. Given a graph $G=(V,E)$ on $n$ vertices, the Maximum $r$-Regular Induced Subgraph (M-$r$-RIS) problem asks for a maximum-sized subset of vertices, $R \subseteq V$, such that the Induced Subgraph on $R$ is $r$-re...
-
Parameterized complexity of the Induced Subgraph problem in directed graphs
Information Processing Letters, 2007Co-Authors: Venkatesh Raman, Somnath SikdarAbstract:In this Letter, we consider the parameterized complexity of the following problem: Given a hereditary property P on digraphs, an input digraph D and a positive integer k, does D have an Induced subdigraph on k vertices with property P? We completely characterize hereditary properties for which this Induced Subgraph problem is W[1]-complete for two classes of directed graphs: general directed graphs and oriented graphs. We also characterize those properties for which the Induced Subgraph problem is W[1]-complete for general directed graphs but fixed parameter tractable for oriented graphs. These results are among the very few parameterized complexity results on directed graphs.
-
fast exponential algorithms for maximum γ regular Induced Subgraph problems
Foundations of Software Technology and Theoretical Computer Science, 2006Co-Authors: Sushmita Gupta, Venkatesh Raman, Saket SaurabhAbstract:Given a graph G = (V,E) on n vertices, the Maximum γ-Regular Induced Subgraph (M-γ-RIS) problems ask for a maximum sized subset of vertices R⊆V such that the Induced Subgraph on R, G[R], is γ-regular. We give an $\mathcal{O}(c^n)$ time algorithm for these problems for any fixed constant γ, where c is a positive constant strictly less than 2, solving a well known open problem. These algorithms are then generalized to solve counting and enumeration version of these problems in the same time. An interesting consequence of the enumeration algorithm is, that it shows that the number of maximal γ-regular Induced Subgraphs for a fixed constant γ on any graph on n vertices is upper bounded by o(2n). We then give combinatorial lower bounds on the number of maximal γ-regular Induced Subgraphs possible on a graph on n vertices and also give matching algorithmic upper bounds. We use the techniques and results obtained in the paper to obtain an improved exact algorithm for a special case of Induced Subgraph Isomorphism that is Induced γ-Regular Subgraph Isomorphism, where γ is a constant. All the algorithms in the paper are simple but their analyses are not. Some of the upper bound proofs or algorithms require a new and different measure than the usual number of vertices or edges to measure the progress of the algorithm, and require solving an interesting system of polynomials.
Kristina Vuskovic - One of the best experts on this subject based on the ideXlab platform.
-
toward Induced Subgraph obstructions to bounded treewidth
arXiv: Combinatorics, 2021Co-Authors: Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Sepehr Hajebi, Pawel Rzązewski, Sophie Spirkl, Kristina VuskovicAbstract:This paper is motivated by the following question: what are the unavoidable Induced Subgraphs of graphs with large treewidth? Aboulker et al. conjectured that for every $k$, every graph with bounded maximum degree and sufficiently large treewidth contains either a subdivision of the $(k\times k)$-wall or the line graph of a subdivision of the $(k\times k)$-wall as an Induced Subgraph. We prove two theorems supporting this conjecture, as follows. 1. For $t\geq 2$, a $t$-theta is a graph consisting of two nonadjacent vertices and three internally disjoint paths between them, each of length at least $t$. A $t$-pyramid is a graph consisting of a vertex $v$, a triangle $B$ disjoint from $v$ and three paths starting at $v$ and disjoint otherwise, each joining $v$ to a vertex of $B$, and each of length at least $t$. We prove that for all $k,t$, every graph of bounded maximum degree and sufficiently large treewidth contains either a $t$-theta, or a $t$-pyramid, or the line graph of a subdivision of the $(k\times k)$-wall as an Induced Subgraph. This affirmatively answers a question of Pilipczuk et al. asking whether every graph of bounded maximum degree and sufficiently large treewidth contains either a theta or a triangle as an Induced Subgraph (where a theta means a $t$-theta for some $t\geq 2$). 2. A subcubic subdivided caterpillar is a tree of maximum degree at most three whose all vertices of degree three lie on a path. We prove that for every subcubic subdivided caterpillar $T$, every graph with bounded maximum degree and sufficiently large treewidth contains either a subdivision of $T$ or the line graph of a subdivision of $T$ as an Induced Subgraph.
-
on triangle free graphs that do not contain a subdivision of the complete graph on four vertices as an Induced Subgraph
Journal of Graph Theory, 2017Co-Authors: Nicolas Trotignon, Kristina VuskovicAbstract:We prove a decomposition theorem for the class of triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an Induced Subgraph. We prove that every graph of girth at least five in this class is 3-colorable.
-
on triangle free graphs that do not contain a subdivision of the complete graph on four vertices as an Induced Subgraph
arXiv: Combinatorics, 2014Co-Authors: Nicolas Trotignon, Kristina VuskovicAbstract:We prove a decomposition theorem for the class of triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an Induced Subgraph. We prove that every graph of girth at least~5 in this class is 3-colorable.
Vadim Zverovich - One of the best experts on this subject based on the ideXlab platform.
-
a semi Induced Subgraph characterization of upper domination perfect graphs
Journal of Graph Theory, 1999Co-Authors: Igor E Zverovich, Vadim ZverovichAbstract:Let β(G) and Γ(G) be the independence number and the upper domination number of a graph G, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every Induced Subgraph H of G. The class of Γ-perfect graphs generalizes such well-known classes of graphs as strongly perfect graphs, absobantly perfect graphs, and circular arc graphs. In this article, we present a characterization of Γ-perfect graphs in terms of forbidden semi-Induced Subgraphs. Key roles in the characterization are played by the odd prism and the even Mobius ladder, where the prism and the Mobius ladder are well-known 3-regular graphs [2]. Using the semi-Induced Subgraph characterization, we obtain a characterization of K1,3-free Γ-perfect graphs in terms of forbidden Induced Subgraphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 31:2949, 1999
-
an Induced Subgraph characterization of domination perfect graphs
Journal of Graph Theory, 1995Co-Authors: Igor E Zverovich, Vadim ZverovichAbstract:Let γ(G) ι(G) be the domination number and independent domination number of a graph (G), respectively. A graph (G) is called domination perfect if γ(H) = ι(H), for every Induced Subgraph H of (G). There are many results giving a partial characterization of domination perfect graphs. In this paper, we present a finite Induced Subgraph characterization of the entire class of domination perfect graphs. The list of forbidden Subgraphs in the charcterization consists of 17 minimal domination imperfect graphs. Moreover, the dominating set and independent dominating set problems are shown to be both NP‐complete on some classes of graphs. © 1995 John Wiley & Sons, Inc. Copyright © 1995 Wiley Periodicals, Inc., A Wiley Company
